PhD theses

Pedestrians, like drivers, generally dislike congestion. This is true for most pedestrian envi- ronments: trains stations, airports, or shopping malls. Furthermore, pedestrian congestion also influences the attractiveness of public transportation networks. Therefore, preventing, or at least limiting, congestion from occurring inside walkable environments is critical. Although the desire to reduce, or limit, congestion appears unquestioned, the solutions to achieve this are challenging and diverse. The range of possible measures goes from adequate design considerations during the construction phase to dynamically controlled devices for managing pedestrian flows. In this thesis we discuss, design, and evaluate several innovative dynamic control strategies dedicated to managing pedestrian flows. Installing hardware is not sufficient, thorough understanding of the dynamics taking place inside a given infrastructure is critical. Furthermore, a framework for ensuring communication between the measurement devices, control algorithm and hardware is needed. For road traffic, this frame- work is called Dynamic Traffic Management Systems (DTMS). The specification of the pedestrian counterpart is discussed in this thesis: Dynamic Pedestrian Management Systems (DPMS). We compare the specificities of DTMS to DPMS and emphasize the characteristics of pedestrian dynamics. Furthermore, we propose several control strategies dedicated to pedestrian flows and evaluate their effectiveness. The first is gating, inspired from traffic lights and ramp metering in road networks. The second is the usage of flow separators to prevent bidirectional pedestrian flow from occurring. The third and final strategy we propose exploits moving walkways, by controlling their speed and direction, to influence pedestrian flows. The different control strategies illustrate the utilisation of the DPMS by simulating different case studies. The first control strategy we propose, gating, provides only minor improvements to the pedestrian dynamics. This occurs since the strategy is not tailored to pedestrian flow characteristics. The second strategy successfully improves pedestrian travel times by dynamically allocating walking space to antagonistic flows. The third strategy, where one flavour of the control algorithm integrates short term predictions, is highly successful at reducing congestion and improving travel times. The utilisation of moving walkways by the predictive algorithm emphasizes the trade-off between decreasing travel time and reducing congestion. Nevertheless, the computational cost is high. Finally, for all control strategies and all algorithms, some users are penalized, while others benefit from the strategy. Thanks to the different control strategies proposed in this thesis, we emphasize the need for control strategies which address pedestrian specific situations. Three specificities are identified: user compliance, available choices, and the complexity of pedestrian motion. Addressing these aspects is critical to develop successful strategies. The strategies we discuss can be applied in any pedestrian context. Nevertheless, the potential of the strategies developed in this thesis are still underexplored. Significant improvements can be expected with further development and calibration of the control algorithms. Furthermore, practical applications could be implemented with limited cost since most of the components for using simple strategies already exist.

The objective of this thesis is to develop a general methodology to incorporate a disaggregate demand representation in supply-oriented optimization problems that allows to capture the interplay between the behavior of individuals and the decisions to be optimized. To this end, we propose a modeling framework for the integration of discrete choice models (DCM) in mixed-integer linear problems (MILP), and we show that it is both flexible and operational on realistic instances. In particular, we develop algorithms to enhance the tractability of the framework, and we illustrate its applicability with two relevant optimization problems that arise in a great deal of contexts. The demand functions generated from DCM are highly non-linear and non-convex, and are not always available in closed form. In this thesis, we avoid the use of such functions by specifying the preference structure of DCM directly in terms of the related structural equations (utility functions). We rely on simulation in order to handle the probabilistic nature of these equations by drawing from the distribution of the associated random component. This yields a mixed-integer linear set of constraints that can be embedded in any MILP formulation. The only requirement is that the decisions to be optimized that are also explanatory variables of the DCM, and therefore capture the interactions, appear linearly in the structural equations. The disaggregate nature of DCM, together with the associated simulation-based linearization, comes with a high computational complexity. Motivated by the decomposable structure of the framework along the two dimensions it is built on, the individuals and the simulation draws, we characterize a Lagrangian decomposition scheme that enables to solve larger instances, at least approximatively. Indeed, the performed tests show that near-optimal solutions are obtained in a much reduced computational time. The framework is sufficiently general to accommodate a wide variety of relevant optimization problems. The main strength is that the DCM does not need to be tailored to the formulation, i.e., it can be taken as such from the literature. In particular, it does not have to be a DCM that relies on simplistic assumptions, such as the logit model, and more advanced DCM such as mixtures of logit models can be integrated. In this thesis, we consider and solve two problems in order to illustrate the versatility of the framework, namely operator-centric profit maximization and traveler-centric design of a transportation system. The former assumes an operator that offers services to a market with the aim of maximizing its profit. The latter formulates the pricing and design of a transportation system such that a measure of welfare is maximized. The key quantitative element of welfare analysis in the context of DCM, the expected maximum utility, is readily available in the framework. This represents a significant advantage because it allows not to deal with the complex non-linear formulations of this quantity as provided by discrete choice theory. In summary, this thesis makes relevant contributions on the integration of DCM in MILP, and shows their applicability by relying on real-world optimization problems. The proposed models and algorithms shed some light on the benefits of incorporating individual behavior in operational decisions for any industry with close interactions between the demand and the supply.

The focus of this thesis is to develop methods to address research challenges related to correlation patterns in discrete choice models. In the context of correlations within alternatives, we extend the novel methodology of the multiple indicator solution (MIS) to deal with endogeneity, and show, through its theoretical derivation, that it is applicable when there are interactions between observed and unobserved variables. In the context of correlations between alternatives, we discuss the importance of using models that can capture them, such as cross nested logit models. We show, through real world examples, that ignoring these correlation patterns can have severe impacts on the obtained demand indicators, and that this can lead to wrong decisions by practitioners. We also address the challenge of using revealed preference data, where the attributes of the non-chosen alternatives are unavailable, and propose a solution based on multiple imputations of their empirical distributions. In the thesis, we also contribute to the existing literature by gaining a better understanding of private motorized modes, in terms of modal split and purchases of new cars. Related to modal split, we use a mode choice case study in low density areas of Switzerland. We find that ignoring the car-loving attitude of individuals leads to incorrect value of time estimates and elasticities, which might have severe implications in the pricing schemes of public transportation, for example. Related to the purchase of new cars, we use data from new car acquisitions in France in 2014, and focus on hybrid and electric vehicles. We find elasticities to price that are in line with the literature, and willingness to pay values in line with the market conditions. We also study the impact of different future policy scenarios and find that the sales of new electric vehicles could reach around 1% as a result of a major technological innovation that would render electric vehicles less expensive. In the last part of the thesis, we propose the discrete-continuous maximum likelihood (DCML) framework, which consists in estimating discrete and continuous parameters simultaneously. This innovative idea, opens the door to new research avenues, where decisions that were usually taken by the analyst can now be data driven. As an illustration, we show that correlations between alternatives can be identified at the estimation level, and do not need to be assumed by the analyst. The DCML framework consists in a mixed integer linear program (MILP) in which the log-likelihood estimator is linearized. This linearization might be useful to estimate parameters of other discrete choice models for which the log-likelihood function is not concave (and therefore global optimality is not insured by the optimization algorithms), since for an MILP, a global optimum is guaranteed. We use a simple mode choice case study for the proof-of-concept of the DCML framework, and use it to investigate its strengths and limitations. The preliminary results presented in the thesis seem very promising. To summarize, we develop methods to deal with correlations in discrete choice models that are relevant to real world problems, and show their applicability by using transportation examples. The contributions are therefore both theoretical and applied. The new methods proposed open the door to new research directions in the discrete choice field.

Unexpected disruptions occur for many reasons in railway networks and cause delays, cancellations, and, eventually, passenger inconvenience. This thesis focuses on the railway timetable rescheduling problem from a macroscopic point of view in case of large disruptions, such as track unvailabilities due to, e.g., rolling stock malfunction or adverse weather conditions. Its originality is to consider three objectives when designing the so-called disposition timetable: the passenger satisfaction, the operational cost and the deviation from the undisrupted timetable. These goals are usually incompatible: for instance, the best possible service for the passengers may also be the most expensive option for the railway operator. This inadequacy is the key motivation for this thesis. The problem is formally defined as a multi-objective Integer Linear Program and solved to optimality on realistic instances. In order to understand the trade-offs between the objectives, the three-dimensional Pareto frontier is approximated using epsilon-constraints. The results on a Dutch case study indicate that adopting a demand-oriented approach for the management of disruptions not only is possible, but may lead to significant improvement in passenger satisfaction, associated with a low operational cost of the disposition timetable. For a more efficient investigation of the multiple dimensions of the problem, a heuristic solution algorithm based on adaptive large neighborhood search is also presented. The timetable is optimized using operators inspired directly from recovery strategies used in practice (such as canceling, delaying or rerouting trains, or scheduling additional trains and buses), and from optimization methods (e.g., feasibility restoration operators). Results on a Swiss case study indicate that the proposed solution approach performs well on large-scale problems, in terms of computational time and solution quality. In addition, a flexible network loading framework, defining priorities among passengers for the capacitated passenger assignment problem, is introduced. Being efficient and producing stable aggregate passenger satisfaction indicators (such as average travel time), it is used in an iterative manner for the evaluation from the passenger perspective of the timetable provided by the rescheduling meta-heuristic. The timetable rescheduling problem is a hard problem and this thesis makes significant methodological and practical contributions to the design of passenger-centric disposition timetables. It is the first attempt to explicitly integrate multiple objectives in a single framework for railway timetable rescheduling, as the state-of-the-art usually neglects passenger considerations, or considers them only implicitly. Further, the use of practice-inspired optimization methods allows railway operators to easily implement the results of the proposed framework.

This thesis develops a unified framework for modeling and solving various classes of rich routing problems with stochastic demands, including the VRP and the IRP. The work is inspired by the problem of collecting recyclables from sensorized containers in Geneva, Switzerland. We start by modeling and solving the deterministic single-period version of the problem, which extends the class of VRPs with intermediate facilities. It is formulated as an MILP which is enhanced with several valid inequalities. Due to the rich nature of the problem, general-purpose solvers can only tackle instances of small to medium size. To solve realistic instances, we propose a meta-heuristic approach which achieves optimality on small instances, exhibits competitive performance in comparison to state-of-the-art methods, and leads to important savings in the state of practice. Moreover, it highlights and quantifies the savings from allowing open tours, in which the vehicles' origin and destination depots do not coincide. To integrate demand stochasticity, we extend the problem to an IRP over a finite planning horizon. Demand can be non-stationary and is forecast with any model that provides the expected demands and the standard deviation of the error terms, where the latter are assumed to be iid normal. The problem is modeled as an MINLP, in which the dynamic stochastic information impacts the cost through the probability of container overflows and route failures. The solution methodology is based on Adaptive Large Neighborhood Search (ALNS) which integrates a specialized forecasting model, tested and validated on real data. The computational experiments demonstrate that our ALNS exhibits excellent performance on VRP and IRP benchmarks. The case study, which uses a set of rich IRP instances from Geneva, finds strong evidence of the added value of including stochastic information in the model. Our approach performs significantly better compared to alternative deterministic policies in limiting the occurrence of overflows for the same routing cost. We also analyze the solution properties of a rolling horizon approach in terms of empirical lower and upper bounds. This approach is generalized in a unified framework for rich routing problems with stochastic demands, where we drop the assumption of iid normal error terms. We elaborate on the effects of the stochastic dimension on modeling, with a focus on stock-outs/overflows and route failures, and the cost of the associated recourse actions. Tractability is achieved through the ability to precompute or partially preprocess the bulk of the stochastic information, which is possible for a general inventory policy under mild assumptions. We propose an MINLP formulation, illustrate applications to various problem classes from the literature and practice, and demonstrate that certain problems, e.g. facility maintenance, where breakdown probabilities accumulate over the planning horizon, can be seen through the lens of inventory routing. The case study is based on the waste collection IRP instances cited above and on a new set of instances for the facility maintenance problem. On the first set, we analyze the effects of our assumptions on tractability and the objective function's representation of the real cost. On the second set, we demonstrate the framework's ability to achieve the same level of occurrence of breakdowns for a significantly lower routing cost compared to alternative deterministic policies.

Route choice analysis concerns the understanding, modeling and prediction of the itinerary of an individual who travels from one position to another. In this thesis we elaborate on aggregate route choice analysis. The objective is the development of a flexible framework for analysing and predicting route choice behavior. The research is motivated by the need to reduce the structural complexity of the state of the art route choice models and aims at facilitating their practical applications. Our approach is inspired by the environmental images of the physical space that individuals form in their minds. The framework is based on elements designed to mimic these representations. In this context, we introduce the concept of mental representation item (MRI ) in route choice analysis. The MRIs represent the strategic decisions of individuals and constitute the building blocks of the alternatives of the aggregate model. They play the same role as the links do in the specification of a disaggregate model. In contrast to the links, the MRIs are not dictated by the definition of the network model. Their definition depends on the analyst, allowing her to control the trade-off between complexity and realism, according to the needs of the specific application and the data availability. We start by presenting a methodology for the definition of operational random utility models based on MRIs . As a proof of concept, we define a simple model for the town of Borl\"ange, in Sweden, and test it using real data. We further discuss applications of the proposed model to traffic assignment and route guidance. The results demonstrate that the use of simple methods leads to a meaningful model that can be estimated and used in practice. We then investigate the capability of the proposed MRI model to derive route choice indicators for practical applications, through comparison with a state of the art disaggregate model. The recursive logit (RL) model is selected as the representative of the existing disaggregate approaches. An extension of the MRI framework with the definition of a graph of MRI elements is presented and methods to derive route choice indicators from a model that does not correspond to the intended level of analysis are proposed. The evaluation of the models' performance at the aggregate level shows that the MRI model should be preferred against a disaggregate model that is subjected to aggregation, if an aggregate analysis is of interest. To demonstrate the generalization and applicability of the framework, we use a dataset from the city of Qu\'ebec, in Canada. Our approach is motivated by (i) the additional complexity in the definition of the model due to the size of the city, and (ii) the lack of a detailed disaggregate network model. The proposed model is (i) operationalized using simple techniques, (ii) compatible with the standard estimation procedures and (iii) by integration with the RL model, readily applied to the prediction of flows on the major segments of the network. This model is not as simple as the first MRI model, yet still of much lower structural complexity in comparison with the disaggregate approach, allowing for fast computation times. The results demonstrate its capability to reproduce the patterns in the observed flows. This thesis contributes by (i) gradually addressing the challenges related to the definition, operationalization and application of aggregate route choice models and (ii) demonstrating their applicability and validity using real data. This is important as it has the potential (i) to reduce the structural complexity of the state of the art approaches, and (ii) to allow for project-specific models that do not require a detailed network model. In a broader context, the framework is relevant and can be adapted to pedestrian route and activity choice modeling.

Various countries and communities are defining or rethinking their energy strategy driven by concerns for climate change and security of energy supply. Energy models, often based on optimization, can support this decision-making process. In the current energy planning practice, most models are deterministic, i.e. they do not consider uncertainty and rely on long-term forecasts for important parameters. However, over the long time horizons of energy planning, forecasts often prove to be inaccurate, which can lead to overcapacity and underutilization of the installed technologies. Although this shows the need of considering uncertainty in energy planning, uncertainty is to date seldom integrated in energy models. The main barriers to a wider penetration of uncertainty are i) the complexity and computational expense of energy models; ii) the issue of quantifying input uncertainties and determining their nature; iii) the selection of appropriate methods for incorporating uncertainties in energy models. To overcome these limitations, this thesis answers the following research question How does uncertainty impact strategic energy planning and how can we facilitate the integration of uncertainty in the energy modeling practice? with four novel methodological contributions. First, a mixed-integer linear programming modeling framework for large-scale energy systems is presented. Given the energy demand, the efficiency and cost of energy conversion technologies, the availability and cost of resources, the model identifies the optimal investment and operation strategies to meet the demand and minimize the total annual cost or greenhouse gas emissions. The concise formulation and low computational time make it suitable for uncertainty applications. Second, a method is introduced to characterize input uncertainties in energy planning models. Third, the adoption of a two-stage global sensitivity analysis approach is proposed to deal with the large number of uncertain parameters in energy planning models. Fourth, a complete robust optimization framework is developed to incorporate uncertainty in optimization-based energy models, allowing to consider uncertainty both in the objective function and in the other constraints. To evaluate the impact of uncertainty, the presentation of the methods is systematically associated to their validation on the real case study of the Swiss energy system. In this context, a novelty is represented by the consideration of all uncertain parameters in the analysis. The main finding is that uncertainty dramatically impacts energy planning decisions. The results reveal that uncertainty levels vary significantly for different parameters, and that the way in which uncertainty is characterized has a strong impact on the results. In the case study, economic parameters, such as the discount rate and the price of imported resources, are the most impacting inputs; also, parameters which are commonly considered as fixed assumptions in energy models emerge as critical factors, which shows that it is crucial to avoid an a priori exclusion of parameters from the analysis. The energy strategy drastically changes if uncertainty is considered. In particular, it is demonstrated that robust solutions, characterized by a higher penetration of renewables and of efficient technologies, can offer more reliability and stability compared to investment plans made without accounting for uncertainty, at the price of a marginally higher cost.

The focus of the thesis is the utilization of the data collected using state-of-the-art tracking technologies for the characterization and modeling of pedestrian movements. In this context, the main objectives are the development of (i) data-driven definitions of fundamental variables and (ii) data-inspired mathematical formulations of fundamental relationships characterizing pedestrian traffic. The motivation of this research comes from the analysis of a real dataset collected in the train station in Lausanne, Switzerland. To collect the raw data, a large-scale network of smart sensors has been deployed in the station. We consider this case study to illustrate and validate our methodology. The definitions of fundamental traffic variables (speed, density and flow), existing in the literature are extended through a data-driven discretization framework. The framework is based on spatio-temporal Voronoi diagrams, designed using pedestrian trajectory data. The new definitions are (i) independent from an arbitrarily chosen discretization, (ii) appropriate for the multi-directional composition of pedestrian traffic, (iii) able to reflect the heterogeneity of pedestrian population and (iv) applicable to pedestrian trajectories described either analytically or as a sample of points. The performance of the approach and its advantages are illustrated empirically. Our approach outperforms the existing methodologies from the literature, in terms of the smoothness of the results, and in terms of the robustness with respect to the simulation noise and sampling frequency. To represent fundamental relationships of pedestrian traffic, we introduce probabilistic speed-density models. The approach is motivated by the high scatter in the data that we have analyzed. To characterize the observed pattern we relax the homogeneity assumption of the equilibrium relationships, and propose two models. The first model is based on distributional assumptions. The second model is more advanced, and it includes structures that are designed to capture specific aspects of the walking behavior. Various empirical tests validate the specification of both models. Contrasted with existing approaches, they yield a more realistic representation of the empirically observed phenomena. This thesis contributes with respect to the utilization of data potential in modeling of fundamental aspects related to pedestrian traffic. This becomes essential in the context of the growing data revolution and interconnected technologies that can help improve the safety and convenience of pedestrians. The methodological framework is fairly general, and it can be adapted to various pedestrian facilities.

The focus of this thesis is to include the passengers and their behavior inside the train timetable design. This is done through three main objectives: timetable design based on passenger satisfaction, exploitation of hybrid cyclicity and choice based revenue optimization. At first, a new Passenger Centric Train Timetabling Problem is introduced into the planning horizon of the passenger railway service. This problem is inter-disciplinary. It combines the discrete choice theory, that models the passengers' behavior, and operations research, that decides on the departure times of the trains (i.e. the timetable). The attributes affecting the passengers' choices with respect to the operated timetable are quantified into a single variable of passenger satisfaction. The objective of the proposed model is the trade-off between the profit of the train operating company and the overall satisfaction of the passengers. The problem is tested on the case study of the morning peak hours in S-train network of Canton Vaud in Switzerland. The results not only confirm that the passenger centric timetables outperform the operational timetable of Swiss Federal Railways (SBB), but they also demonstrate that there is a considerable gap between the performance of the cyclic and the non-cyclic timetable. The cause of this gap are the cyclicity constraints and therefore, new types of hybrid cyclicity are proposed and tested. The aim of the hybrid cyclic timetables is to provide similar level of flexibility (passenger satisfaction) as the non-cyclic timetables while keeping a certain level of regularity (cyclicity). The regularity is taken care of by the design and the flexibility is evaluated upon solving of the previously defined Passenger Centric Train Timetabling Problem. The new types of timetables are tested against the existing types on the case study of one day in the whole network of Israeli Railways. It is shown that the hybrid cyclic timetable can achieve both benefits (regularity and flexibility) at the same time. In the last part of this thesis, the passengers' actual choices are obtained through a discrete choice model. The model takes into account fundamental principles in economics such as demand elasticity, ticket price and opt-out option for passengers. Therefore, the probabilistic Elastic Passenger Centric Train Timetabling Problem provides more realistic solutions. Moreover, since the choice is explicitly modeled, the new problem is integrated with a ticket pricing, in order to improve the level of service. In other words, to prevent overcrowding or to secure the service for passengers who need it the most, etc. To summarize, this thesis makes significant contributions in the conceptual design of timetables by taking into account the passengers and their wishes. Indeed, the planning from the operator's point-of-view is in the state-of-the-art, whereas the passengers have been neglected or have been considered only as an abstract concept.

This thesis addresses two modeling problems related to pedestrian flows in train stations, namely that of estimating pedestrian origin-destination demand in rail access facilities, and that of describing the propagation of pedestrians in walking facilities. For both problems, a mathematical framework is developed at the aggregate level, describing pedestrians in terms of groups with the same departure time, origin and destination. The proposed demand estimator is probabilistic and accounts for within-day dynamics as well as for natural fluctuations across days. It is inspired by estimation methodologies that are used in the context of vehicular traffic. Critically, the proposed methodology takes the train timetable and ridership data into account, significantly improving the accuracy of the estimates. Other information sources, such as link flows or sales data, can also be incorporated. To describe the propagation of pedestrians, walkable space is considered as a network of pedestrian streams that interact locally. Based on the continuum theory for pedestrian flow and the cell transmission model, a computationally efficient model is obtained that can be used under a wide range of traffic conditions. An optional extension allows considering anisotropic flow, where the walking speed depends on the walking direction. Such a formulation is advantageous in particular at high densities. Throughout the thesis, a case study of Lausanne railway station is considered. A detailed discussion of the usage and level-of-service of its rail access facilities is provided, underlining the performance and practical applicability of the proposed modeling framework. The contribution of the thesis is fourfold. First, it provides a dedicated estimation methodology for pedestrian OD demand in train stations. Second, it proposes a novel macroscopic network loading model for congested and multi-directional pedestrian flows. Third, it presents a detailed case study of a Swiss train station, for which a rich data set is collected. Finally, it applies the aforementioned modeling framework to that case study, and provides practical guidance for its use in the planning and dimensioning of rail access facilities. Beyond train stations, the developed modeling framework can be readily applied to various other pedestrian facilities, such as airports, shopping malls, stadiums or urban walking areas. For instance, it may be used to support the organization, planning and design of such facilities, to safely and efficiently manage pedestrian flows using real-time monitoring and control, or to assess and optimize the safety both during normal use and in case of emergency.

This thesis develops models of activity and destination choices in pedestrian facilities from WiFi traces. We adapt the activity-based travel demand analysis of urban mobility to pedestrians and to digital footprints. We are interested in understanding the sequence of activities and destinations of a pedestrian using discrete choice models and localization data from communication antennas. Activity and destination choice models are needed by pedestrian facilities for decision aid when building new infrastructure, modifying existing infrastructures, or locating points of interest. Understanding demand for activities is particularly important when facing an increasing number of visitors or when developing new activities, such as shopping or catering. Data from existing sensors, such as WiFi access points, are cheap and cover entire facilities, but are imprecise and lack semantics to describe moving, stopping, destinations or activities carried out at destinations. Thus, understanding pedestrian behavior first requires to observe the actual behavior and detect stops at destinations, and second to model the behavior. Part I of this thesis focuses on activity-episode sequence detection. We develop a Bayesian approach to merge raw localization data with other data sources in order to take into account the imprecision and describe activity-episode sequences. This approach generates several activity-episode sequences for a single individual. Each activity-episode sequence is associated with a probability of being the true sequence. The prior represents the attractivity of the different points of interest surrounding the measurement and allows the use of a priori information from other sources of data (register data, point-of-sale data, counting sensors, etc.). Part II proposes models for activity and destination choices. The joint choice of activity type and activity timing is modeled by seeing a sequence of activity episodes as a path in an activity network. Time is considered as discrete. Unlike traditional models, our model is not tour-based, starting and ending at the home location, since the daily ``home''activity is meaningless in our context. The choice set contains all combinations of activity types and time intervals. The number of different paths is thus very large (increasing with time resolution and disaggregation of types of activities). Inspired by route choice models, we use a Metropolis-Hastings algorithm for the sampling of paths to generate the choice set. An importance sampling correction of the utility allows the estimation of unbiased model parameters without enumerating the full choice set. While the activity path model describes the choice of an activity type in time, the location where the activity is performed is modeled with a destination choice model conditional on the activity type. Our approach accounts for the panel nature of the data and deals with serial correlation between error terms. Using real WiFi data collected on the EPFL campus, we detect pedestrian activity-episode sequences, estimate an activity path choice model and develop a destination choice model for a specific activity type: eating. Knowing that the individual has decided to eat, which restaurant does she choose? This conditional destination choice model includes in its utility the cost of menus, available types of foods and drinks, distance from a previous activity episode, socioeconomic characteristics and habits.

This thesis proposes novel methods to model individual behavior. We consider both static and dynamic approaches to deal with the complexity of representing the decision process. Attitudes, perceptions, lifestyles but also past decisions or expectations are key factors affecting the choice behavior. This thesis aims at accurately representing these factors and assess thoroughly their impact on human decisions. Part I focuses on the development of static models. More specifically, advanced models are developed to assess the effect of psychological factors, such as attitudes, perceptions or lifestyles on decisions. To address the important, however difficult, task to quantitatively evaluate these factors, we propose contributions in three different research directions: data exploitation, modeling and forecasting. In terms of data exploitation, we use a new type of measures of perceptions. Standard approaches rely importantly on the use of opinion statements conceived by the survey designer, where respondents have to indicate their level of agreement. To address the subjectivity of this approach, we propose to use adjectives freely reported by individuals as measurements of their perceptions. Regarding modeling, we include psychometric indicators into integrated choice and latent class models, in order to better characterize the behavior of individuals belonging to different population segments. The main contribution lies in the simple formulation of the model, which is analogous to formulations considered in integrated choice and latent variable models and does not consider intermediate latent variables. The estimation process is hence considerably easier. One of the main purposes of a mathematical model is its application for prediction. However many studies do not systematically propose a thorough analysis of a model's benefits in terms of forecasting. Regarding that last aspect, we present a complete procedure to forecast the demand of a technology which is new on the market, from the design of a survey to the analysis of demand forecasting. A prediction framework is obtained from stated preferences data combined with market information. Part II integrates dynamic aspects into demand forecasting. We develop advanced models involving two important time-dependent factors of decisions: past choices and expectations about the future. In the first case, we develop a forecasting framework which explains product switching decisions with a first-order Markov chain. The main contribution of this model is the assessment of the impact of market events, supply information or policies on replacement behavior. A validation analysis shows that the framework is highly precise in terms of predicting demand. In the second case, a dynamic discrete-continuous choice model is developed in order to assess the impact of expectations about the future on individuals' present choices. The framework combines two advanced methodologies of the demand modeling field: discrete-continuous choice modeling and dynamic choice modeling. To the best of our knowledge this is the first example of a dynamic discrete-continuous choice model for multiple product acquisition and usage. The methodological developments of this thesis have been motivated by various interesting applications. The models of Chapter 4 allows for a characterization of the perception of comfort in public transportation and the evaluation of positive or negative perceptions of comfort on transportation mode decisions. The data is based on a revealed preferences survey in low-density areas of Switzerland. The model of Chapter 5 allows for the identification of population segments with different mode choice behaviors in two different locations, namely in low-density areas of Switzerland and in the city of Nice (France). Revealed preferences data are used in both cases. The model of Chapter 6 aims at forecasting the demand for electric vehicles on the Swiss market, based on both revealed and stated preferences data. The framework of Chapter 9 allows to evaluate the future demand for different car segments in the whole French market for five years ahead. The data is based on a large-scale survey of new purchases in France for several years. The model of Chapter 10 is designed to model decisions regarding car ownership, choice of fuel type and usage based on the registers of cars and individuals in Sweden.

In the operations research (OR) literature on port operations planning, there are a significant number of studies addressing decision problems in the context of container terminal management. Bulk terminals on the other hand, have been largely ignored. In this thesis, we study some of the key decision problems such as the berth allocation problem and the yard assignment problem in the bulk context. The berth allocation problem (BAP) in bulk ports differs from that in container terminals, primarily because it is necessary to explicitly account for the cargo type on the vessel and the locations of the fixed equipment facilities such as con- veyors and pipelines that are installed at only certain sections along the quay. We develop exact and heuristic algorithms to solve the BAP in bulk ports. The results based on instances inspired from real bulk port data look promising and suggest that the proposed methods can be successfully used to improve the op- erational efficiency of berth scheduling in bulk ports. The BAP model is later extended and solved in integration with the yard assignment problem, that is, the problem of assigning different cargo types to specific locations in the yard. We propose a sophisticated exact solution algorithm based on the branch-and-price framework to solve the combined problem of berth allocation and yard assignment, which in all the previous studies related to container terminals has been solved using metaheuristics. Computational results based on real bulk port data suggest that the proposed algorithm can be successfully used to solve realistic sized instances in a computational time that is reasonable enough for the algorithm to be actually implemented and put into practice at the port. Another key challenge in port operations planning is to address the enormous amount of uncertainty on account of factors such as weather conditions, mechanical problems and labor inefficiency among others. A stochastic disturbance can possibly render the planned schedules infeasible, thus incurring high costs to the port. In the current literature, there are very few studies related to handling uncertainty in port operations. In this thesis, we propose innovative models and solution techniques to handle uncertainty in scheduling, based on both proactive and reaction-based approaches. We solve the berth allocation problem on a rolling planning horizon for a given planned baseline schedule and uncertainty in the arrival times and handling times of the vessels. The schedule is updated in response to disruptions as the actual arrival and handling times of the vessels are revealed in real-time. We propose recovery algorithms based on re-optimization and a smart greedy approach to reassign and reschedule the vessels, with the objective to minimize the total realized costs of the modified berthing schedule. The uncertainty in the yet-to-be-revealed part of the information is modeled by making appropriate assumptions about the probability distributions of the uncertain parameters derived from past data. The results suggest that our proposed methodology can significantly reduce the incurred costs as compared to the ongoing practice of reassigning vessels at the port. To demonstrate the complexity in handling uncertainty in a proactive manner, we do a theoretical analysis of the most basic scheduling problem in the literature, that is, the single machine scheduling problem. In the context of port operations planning, the problem is analogous to the discrete berth allocation problem with a single berth that can handle at most one vessel at a given time. In all the previous studies on robust scheduling, the uncertainty in the release times of the jobs is largely ignored. We consider uncertainty in both the release times and the processing times of the jobs, discuss important properties of robust scheduling in the context of the single machine scheduling problem, and propose heuristics to generate robust schedules. To summarize, this thesis makes significant fundamental contributions in both methodology and applications of OR. On the application side, we study the decision problems arising in bulk terminals, and propose innovative methods to solve these problems. On the methodological front, we address the prob- lem of handling uncertainty in transportation and logistics systems planning in specific, and scheduling problems in general. Finally, the research presented in this thesis opens up several interesting and challenging possibilities for future research, particularly in the field of port operations planning.

This thesis investigates methodologies for improving the demand responsiveness of transportation systems through flexibility. The methodologies propose advances both in demand and supply models having a focus on supply-demand interactions. The demand side enables to understand the underlying travel behavior and is important to identify the most important aspects of flexibility that needs to be offered with new transportation alternatives. Supply models that integrate supply-demand interactions lead to more efficient and flexible decision support tools with integrated decision problems. Furthermore the supply models enable to understand the impact of flexibility on transportation operations with appropriate representation of flexibility aspects. The main study area of the thesis is air transportation however we believe that the methodological contributions of the thesis are not limited to any mode and have the potential to provide improvements in various systems. In the context of demand modeling, advanced demand models are studied. In the first place, hybrid choice models are developed in the context of a mode choice study motivated by a rich data set. Attitudes and perceptions of individuals are integrated in choice modeling framework and an enhanced understanding of preferences is obtained. Secondly, an air itinerary choice model is developed based on a real dataset. A mixed revealed preferences (RP) and stated preferences (SP) dataset is used for the estimation of the demand model. A demand model is obtained with reasonable demand elasticities due to the existence of the SP data. Advances in demand models can be exploited early in the planning phase when deciding on the capacity. For this matter an integrated airline scheduling, fleeting and pricing model is studied with explicit supply-demand interactions represented by the air itinerary choice model. The integrated model simultaneously decides on schedule design, fleet assignment, pricing, spill, and seat allocation to each class. Several scenarios are analyzed in order to understand the added-value of the integrated model. It is observed that the simultaneous decisions on capacity and revenue bring flexibility in decision making and provide higher profitability compared to state-of-the art models. The main reference model is called the sequential approach that solves the planning and revenue problems sequentially representing the current practice of airlines. The explicit integration of the demand model brings nonlinearities which cannot be characterized as convexity/concavity. For the solution of the model a heuristic method is implemented which iteratively solves two sub-problems of the integrated model. The first sub-problem is an integrated schedule planning model with fixed prices and the second sub-problem is a revenue management problem with fixed capacity. The heuristic is found to provide better quality feasible solutions, in considerably reduced computational time, compared to the mixed integer nonlinear solver BONMIN. Local search techniques are embedded in the heuristic method which enable to obtain better feasible solutions compared to the sequential approach in reasonable computational time even for instances that are similar to real flight networks. In order to reduce the complexity of the problem a logarithmic transformation of the logit model is proposed. The transformation results with a stronger formulation of the revenue problem. Price is the only explanatory variable of the logit model that is defined as a decision variable of the optimization model. However the methodology is flexible for other specifications. The reformulation of the model is again a mixed integer non-convex problem however as illustrated with examples and the airline case study, the model can be handled easier. In order to obtain valid bounds on the revenue a piecewise linear approximation is proposed for the non-convexities in the model. In the last part of the thesis, we focus on analyzing the impact of flexibility by a new design of aircraft called Clip-Air. The main property of Clip-Air is the flexible capacity due to the decoupling of the wing and the capsules (cabin). One, two, or three capsules can be attached under the wing and the configuration of Clip-Air can be adapted to the demand volume. Clip-Air is the main motivation for the contributions of the thesis in the context of supply modeling. The developed integrated models are therefore used in order to carry out a comparative analysis between Clip-Air and standard aircraft. It is found that Clip-Air utilizes the available capacity more efficiently and carries more passengers with less allocated capacity for several scenarios. A sensitivity analysis is performed for different realizations of cost figures. In a nutshell it is observed that the solutions are improved as the level of flexibility is increased, in other words as we move from standard systems to flexible alternatives and from classical planning models to integrated models with explicit representation of demand.

In this thesis, we develop methods for modeling route choice behavior using smartphone data. The developing global positioning system (GPS) technology and the popularity of smartphones have revolutionized the revealed preference route choice data collection. Nowadays, smartphones are embedded with various kinds of sensors that are able to provide mobility related information. These sensors include GPS, accelerometer and bluetooth. The recorded raw data is not directly applicable to travel behavior study, information such as the paths and transport modes of travels have to be inferred. The inference procedure is challenging due to the poor quality and the variety of the data. This thesis deals with these challenges by proposing probabilistic methods that account for errors in the data, and fusing various kinds of smartphone data in an integrated framework. Based on the inference methods, a route choice modeling framework exploiting GPS data is developed. The low cost sensors of smartphones observe measurements with significant errors. Moreover, due to practical constraints, such as the limits on smartphone battery volume and the cost of data transmitted via wireless networks, data are usually recorded in a relatively large time interval (low frequency). These drawbacks preclude path identification (a.k.a. map-matching, MM) algorithms that are designed for dense and accurate data from dedicated GPS devices. Therefore, we first propose a probabilistic unimodal MM method that infers the traveled paths from GPS data recorded during a car trip. Instead of deterministically matching a sequence of GPS points to one path, it generates a probabilistic path observation which is composed of a set of candidate paths, and a measurement likelihood for each path. The candidate paths are generated by a candidate path generation algorithm from GPS data. It is capable of dealing with both accurate and dense data (1 second interval) from dedicated GPS devices, and noisy and sparse data (more than 10 seconds interval) from smartphones. A probabilistic measurement model is constructed to calculate the measurement likelihood, which is the likelihood that the observed GPS data is recorded along a given path. The probabilistic measurement model employs structural equation modeling techniques, and the latent status for each measurement is defined as the true location where the measurement is observed. A GPS sensor measurement model relates the status to each GPS measurement; a structural travel model captures the status over time in the network. In this approach, besides geographical coordinates, speed and time recorded from GPS also contribute to the identification of the true path. Applications and analyses on real data illustrate the robustness and effectiveness of the proposed approach. Based on the framework designed for the unimodal MM, a multimodal MM method is developed to deal with a more general problem where the trips can be multimodal and the modes are unknown. We infer both path and mode information simultaneously from various kinds of data. The candidate path generation algorithm is extended to deal with multimodal networks, and to generate multimodal paths, of which a transport mode is associated with each road. The latent status includes both location and mode, and the correlation between them is exploited. For example, if the mode is bus, the path should follow bus routes. Besides the most useful GPS data, acceleration and bluetooth also contribute mobility information, so they are integrated in the probabilistic measurement model by constructing a sensor measurement model for each. ACCEL provides motion status that can be used to infer the transport mode. BT data gives the amount of nearby BT devices, which can be used to recognize, for instance, a public transport environment if there are a lot of BT devices nearby. This approach is flexible in two aspects. First, any kind of sensor data can be integrated as long as a corresponding sensor measurement model is provided. Second, any transport network can be added or removed according to necessity and availability. Data recorded from a trip does not need to be preprocessed into unimodal travel segments, so the risk of wrong segmentation is attenuated. Numerical experiments include map visualizations of some example trips, and an analysis of the performance of the transport mode inference. In the last part of the thesis, we develop a comprehensive and operational route choice modeling framework for estimating route choice models from GPS data. It integrates three components: the probabilistic unimodal MM method for generating probabilistic path observations from GPS data; the “network-free” data approach proposed by Bierlaire & Frejinger (2008) for estimating route choice models from probabilistic path observations; and a new importance sampling based algorithm for sampling path alternatives for the choice model estimation. The proposed path sampling algorithm produces more relevant alternatives by exploiting the GPS data. Numerical analyses using a real transportation network and synthetic choices empirically show that the proposed path sampling algorithm yields more precise parameter estimates than other importance sampling algorithms. The proposed framework accounts for the imprecision in GPS data. The necessary modifications of each method for GPS data are presented. A route choice model estimated from smartphone GPS data shows the viability of applying the proposed route choice modeling framework with real data.

This thesis describes methods to model the land use component of an urban system. Specifi- cally, it proposes methods to model and simulate the location choice of agents (households or firms) and the formation of prices for real estate goods in a city. These methods are based on the application of two main tools: discrete choice models and microsimulation. Modeling urban systems is extremely relevant for project evaluation and policy making, due to the expensive, large and often irreversible nature of interventions at the urban scale. However, this is a complex task because it involves several sub-systems (land use, transport and energy among others) together with a large number of heterogeneous, interacting agents. Location choice and price models are a fundamental component of land use models because they describe the dynamics of the city and the spatial distribution of agents and activities. These models are complex because of the large nature of the problem, the presence of nonlinearities due to location externalities and the quasi-unique nature of the traded goods (locations or dwellings). In general, land use models are often hard to implement due to the large amount of data required to model each and every sub-system, even more if the modeling approach is agent-based or disaggregated. This thesis contributes to the field of land use modeling in four aspects. First, an analysis of the formation of the choice set in problems with a large number of alternatives. The analysis is focused on comparing methods to model the availability of each alternative with explicit choice set formation models. Results show that availability-modeling heuristics are useful when dealing with large choice sets, but may significantly deviate from the explicit model. Second, a model for simultaneous estimation of location choice and real estate price is pro- posed. The model considers that each good in the market is traded in a latent auction, where the potential willingness to pay of all agents determines the transaction price. The proposed approach has the advantage of explaining prices as a function of the willingness to pay of the agents, therefore not being determined by the market conditions of the estimation period, as it happens with hedonic price models. Another advantage comes from the latent nature of the auction, which allows to estimate the model even when detailed data on transaction prices is not available. The model is estimated for the city of Brussels using a double mea- surement equation approach, allowing to estimate the location choice and the price model simultaneously. The proposed approach is compared with other methods, showing better results, especially when available price data is aggregated. Third, a market clearing method for agent-based models is proposed. The approach takes into account the expectations of bidding agents as they observe (and react to) the real estate market conditions. The model assumes that, after adjustment of their expectations, agents bid simultaneously for the available locations. This produces a higher level market clearing that determines the real estate price. The proposed method does not require to solve a fixed point problem to find an equilibrium (or market clearing prices) and thus does not require to group agents in clusters. This makes possible to calculate the expectation adjustment at an individual level, therefore making the approach suitable for application in a microsimulation framework. The proposed model is implemented for the city of Brussels and a simulation is performed for the 2001-2008 period. Results show that the model is able to reproduce the observed trends of spatial distribution of agents and real estate prices. Finally, a case study of a full, integrated land use and transport microsimulation model is presented. The model, implemented in the urban simulation platform UrbanSim and the traffic microsimulator MATSim, is estimated and applied to the city of Brussels. The analysis of the case study is focused on the requirements and difficulties of implementing a full scale land use microsimulator, with a special focus on data collection, data processing, model estimation and calibration of the system. An analysis of the trade-off between level of details, implementation costs and quality of the results is also provided, identifying the major difficulties when implementing large scale urban microsimulation models.

Two classical but crucial and unsolved problems in Computer Vision are treated in this thesis: tracking and matching. The first part of the thesis deals with tracking, studying two of its main difficulties: object representation model drift and total occlusions. The second part considers the problem of point matching between omnidirectional images and between omnidirectional and planar images. Model drift is a major problem of tracking when the object representation model is updated on-line. In this thesis, we have developed a visual tracking algorithm that simultaneously tracks and builds a model of the tracked object. The model is computed using an incremental PCA algorithm that allows to weight samples. Thus, model drift is avoided by weighting samples added to the model according to a measure of confidence on the tracked patch. Furthermore, we have introduced also spatial weights for weighting pixels and increasing tracking accuracy in some regions of the tracked object. Total occlusions are another major problem in visual tracking. Indeed, a total occlusion hides completely the tracked object, making visual information unavailable for tracking. For handling this kind of situations, common in unconstrained scenarios, the Model cOrruption and Total Occlusion Handling (MOTOH) framework is introduced. In this framework, in addition to the model drift avoidance scheme described above, a total occlusion detection procedure is introduced. When a total occlusion is detected, the tracker switches to behavioural-based tracking, where instead of guiding the tracker with visual information, a behavioural model of motion is employed. Finally, a Scale Invariant Feature Transform (SIFT) for omnidirectional images is developed. The proposed algorithm generates two types of local descriptors, Local Spherical Descriptors and Local Planar Descriptors. With the first ones, point matching between omnidirectional images can be performed, and with the second ones, the same matching process can be done but between omnidirectional and planar images. Furthermore, a planar to spherical mapping is introduced and an algorithm for its estimation is given. This mapping allows to extract objects from an omnidirectional image given their SIFT descriptors in a planar image.

This thesis tackles new challenges associated with the disaggregate modeling of the human behavior. Decision-aid tools help in making decisions, by providing quantitative insights on the decisions and associated consequences. They are useful in complex situations where human actors are involved. Inside decision-aid tools, there is a need for explicitly capturing and predicting the human behavior. The prediction of human actions is done through models. Models are simplified representations of the reality, which provide a better understanding of it and allow to predict its future state. They are often too simplistic, with bad prediction capabilities. This is an issue as they generate the outcome of the decision-aid tools, which influence decisions. Good models are required in order to adequately capture the complexity of human actions. Behavioral models appear to be relevant. They allow to translate behavioral assumptions into equations, which make their strength but also their complexity. They have been mainly used in transportation and marketing. Many advances have been recently achieved. On one hand, emerging technologies allow to collect various and detailed data about the human behavior. On the other hand, new modeling techniques have been proposed to handle complex behaviors. Estimation softwares are now available for their estimation. The combination of these advances open opportunities in the field of the behavioral modeling. The motivations of the proposed work are the investigation of the challenges associated with non-traditional applications of the behavioral modeling, the emphasis of multi-disciplinarity, the handling of the behavioral complexity and the development of operational models. Different applications are considered where these challenges appear. The applications are the investors' behavior, the walking behavior and the dynamic facial expression recognition. Challenges are addressed in the different tasks of the modeling framework, which are the data collection, the data processing, the model specification, estimation and validation. The modeling of the investors' behavior consists in characterizing how individuals are taking financial decisions. It is relevant for predicting monetary gains and regulating the market. We propose an hybrid discrete choice framework for modeling decisions of investors performed on stock markets. We focus on the choice of action (buy or sell) and the duration until the next action. The choice of action is handled with a binary logit model with latent classes, while a Weibull regression model is used for the duration until the next action. Both models account for the risk perception and the dynamics of the phenomenon. They are simultaneously estimated by maximum likelihood using real data. The predictive performance of the models are tested by cross-validation. The forecasting accuracy of the action model is studied more in details. Parameters of both models are interpretable and emphasize interesting behavioral mechanisms related to investors' decisions. The good prediction capabilities of the action model in a real context makes it operational. The modeling of the walk apprehends how a person is choosing her next step. It is useful to simulate the behavior of crowds, which is relevant for the urban planning and the design of infrastructures. We specify, estimate and validate a model for pedestrian walking behavior, based on discrete choice modeling. Two main types of behavior are identified: unconstrained and constrained. By unconstrained, we refer to behavior patterns which are independent from other individuals. The constrained patterns are captured by a leader-follower model and by a collision avoidance model. The spatial correlation between the alternatives is captured by a cross nested logit model. The model is estimated by maximum likelihood on a real data set of pedestrian trajectories, manually tracked from video sequences. The model is successfully validated using another data set of bi-directional pedestrian flows. The dynamic facial expression recognition consists in characterizing the facial expression of a subject in a video. This is relevant in human machine interfaces. We model it using a discrete choice framework. The originality is based on the explicit modeling of causal effects between the facial features and the recognition of the expression. Five models are proposed, based on different assumptions. The first assumes that only the last frame of the video triggers the choice of the expression. In the second model, one frame is supposed to trigger the choice. The third model is an extension of the second model. It assumes that the choice of the expression results from the average of expression perceptions within a group of frames. The fourth and fifth models integrate the panel effect inherent to the estimation data and are respectively based on the first and second models. The models are estimated by maximum likelihood using facial videos. Parameters are interpretable. Labeling data on the videos has been obtained using an internet survey. The prediction capabilities of the models are studied and compared, by cross-validation using the estimation data. The results are satisfactory, emphasizing the relevance of the models in a real context. The thesis contributes to fields. Challenges of the behavioral modeling have been investigated in complex contexts. Original and multi-disciplinary modeling approaches have been successfully proposed for each application. Model specifications have been developed to handle the behavioral complexity, allowing to quantify behavioral mechanisms. Operational models are proposed. Complex behavioral models are used in a predictive context and a detailed validation methodology has been set.

This thesis deals with models and methods for large scale optimization problems; in particular, we focus on decision problems arising in the context of seaport container terminals for the efficient management of terminal operations. Large-scale optimization problems are both difficult to handle and important in many concrete contexts. They usually originate from real world applications, such as telecommunication, transportation and logistics, and their combinatorial complexity often represents a major issue; therefore, optimization models are crucial to support the decision making process. In particular, column generation and branch-and-price schemes currently represent one of the most advanced and efficient exact optimization approaches to solve large scale combinatorial problems. However, the increasing size and complexity of practical problems arising in real-world applications motivates the design of new solution approaches able to tackle current optimization challenges. In this thesis, we address two complementary research streams where both methods and applications play an important role. On the one hand, we focus on the specific application of container terminals: we propose a new model for the integrated planning of operations and we provide a heuristic and an exact solution algorithm; the broader objective is to devise solution methods that can be generalized and extended to other applications and domains. On the other hand, we aim to develop new methods and algorithms for general large scale problems and, in this context, we investigate a new column generation framework that exploits the relationship between compact and extensive formulation. In particular, we focus on a class of split delivery vehicle routing problems that generalizes a large number of applications arising in the real world, such as transportation and logistics, including container terminal management. In the context of container terminals, we propose a model for the integrated planning of berth allocation and quay crane assignment: the two decision problems are usually solved hierarchically by terminal planners, whereas in the Tactical Berth Allocation Problem we optimize the two problems simultaneously. We firstly present a mixed integer programming formulation that is embedded into a two-level heuristic algorithm based on tabu search and mathematical programming techniques: our heuristic proves to be very efficient, providing good-quality solutions in a reasonable time. The problem is reformulated via Dantzig-Wolfe decomposition and solved via column generation: we propose an exact branch-and-price algorithm and our implementation, that includes state-of-the-art techniques for the master and the pricing problem, outperforms commercial solvers. Furthermore, the exact approach allows us to provide an interesting experimental comparison between hierarchical and integrated planning: computational tests confirm the added value of integration in terms of cost reduction and efficient use of resources. From a methodological point of view, this dissertation investigates a new column generation concept for difficult large scale optimization problems. In particular, we study a class of split delivery vehicle routing problems that generalizes some interesting features of Tactical Berth Allocation Problem, which are relevant also to other applications such as transportation, logistics and telecommunication. The problem, called Discrete Split Delivery Vehicle Routing Problem with Time Windows, presents two main modeling features: demand is discrete and delivered in discrete orders, opposite to the usual assumption of continuously splittable demand; the service time is dependent on the delivered quantity, opposite to the usual assumption of constant service time, regardless of the quantity. The problem is used to validate and test the new column generation approach studied in this thesis. The proposed framework, called Two-stage column generation, represents a novel contribution to recent advances in column generation: the basic idea is to simultaneously generate columns both for the compact and the extensive formulation. We propose to start solving the problem on a subset of compact formulation variables, we apply Dantzig-Wolfe decomposition and we solve the resulting master problem via column generation. At this point, profitable compact formulation variables are dynamically generated and added to the formulation according to reduced cost arguments, in the same spirit of standard column generation. The key point of our approach is that we evaluate the contribution of compact formulation variables with respect to the extensive formulation: indeed, we aim at adding compact formulation variables that are profitable for the master problem, regardless of the optimal solution of the linear relaxation of the compact formulation. We apply two-stage column generation to the Discrete Split Delivery Vehicle Routing Problem with Time Windows. Computational results show that our approach significantly reduces the number of generated columns to prove optimality of the root node. Furthermore, suboptimal compact formulation variables are detected correctly and a large number of variables is not taken into account during the solution process, thus reducing the size of the problem. However, the additional effort required by such a sophisticated approach makes the method competitive in terms of computational time only for instances of a certain difficulty. To conclude, two-stage column generation is a promising new approach and we believe that further research in this direction may contribute to solve more and more complex large scale optimization problems.

Congestion is a phenomenon that arises in a variety of contexts. The most familiar representation is urban traffic congestion. Nonetheless, phenomenons such as prison cell congestion, hospital bed blocking or, at a cellular scale, ribosome congestion, also arise and affect the performance of the underlying networks. The study of network congestion is therefore of interest in numerous application fields. Analytical mathematical models enable the identification and the quantification of network congestion. Furthermore, these methods can be used to identify strategies that mitigate network congestion, by integrating them within optimization frameworks. Deriving such models is an intricate task. Congested networks involve complex traffic interactions. Providing an analytical description of these intricate interactions is challenging. Furthermore, to identify traffic management strategies that indeed mitigate congestion, these models need to be realistic representations of the underlying process, while remaining computationally tractable such that efficient and operational optimization methods can be derived. This thesis presents an analytical network model based on finite capacity queueing theory. Through a novel state space formulation and the use of structural parameters, the model provides a detailed decomposition of congestion. It describes congestion in terms of its sources, its propagation and dissipation rates as well as its frequency. The model is validated versus existing methods, exact results and simulation results. Particularly tractable formulations are derived for single server bufferless queues in a tandem topology and for single server queues with finite buffers in an arbitrary topology network. Unlike existing models, the proposed model maintains the network topology and the queue capacities exogenous. An urban vehicle traffic model is formulated based on this network model. A detailed formulation, based on national transportation standards, is provided. This model is then used to perform optimization for congested road networks. A traffic signal control problem is formulated and solved for the Lausanne city road network. The signal plans derived are evaluated at the microscopic scale with a calibrated simulation model, and compared to both an existing signal plan for the city of Lausanne and to signal plans derived by other methods. The proposed plans delay the propagation of congestion, and lead to improved performance measures. The contributions in the urban transportation field are two-fold. Firstly, the proposed model considers a set of intersections and analytically captures the interactions between queues, contrarily to existing analytic queueing models for urban networks which are formulated for a single intersection, and thus do not take such interactions into account. Secondly, although there is a great variety of signal control methodologies in the literature, there is still a need for solutions that are appropriate and efficient under saturated conditions, where the performance of signal control strategies and the formation and propagation of queues are strongly related. To the best of our knowledge, the existing strategies have not taken urban spillbacks analytically into account. A framework to perform simulation-based optimization, which combines structural information from the analytical queueing model and microscopic information from an urban traffic simulation model for the city of Lausanne, is presented. The framework resorts to a derivative-free trust region algorithm. It is used to solve a traffic signal control problem. With this method well-performing signal plans can be identified given a tight computational budget. By combining a traditionally used functional metamodel with an applicationspecific analytical structural model, this algorithm overcomes the need for a substantial initial sample, and provides meaningful trial points since the very first iterations. A network model is also formulated and used to evaluate congestion for two other applications. Firstly, the phenomenon of bed blocking in a network of operative and post-operative units of the Geneva University Hospitals is investigated. Three main sources of bed blocking are identified, and their impact upon the different hospital units is quantified. We go beyond existing analytical queueing methods that have been used in the health care sector by allowing for networks with an arbitrary topology and with an arbitrary number of queues with finite capacity. Furthermore, the detailed performance measures provided by this approach respond to a recently stated need for methods that quantify in-patient bed blocking. Secondly, the model is formulated for a protein synthesis network, where the traffic of ribosomes along mRNA (messenger ribonucleic acid) strands is of interest. This protein synthesis model consists of a system of linear and quadratic equations, which is a particularly simple and tractable formulation. Unlike other protein synthesis models, this formulation is numerically well-conditioned for highly congested scenarios, suitable for large-scale instances, and can be evaluated using simple numerical techniques.

In this thesis, we address different aspects of the airline scheduling problem. The main difficulty in this field lies in the combinatorial complexity of the problems. Furthermore, as airline schedules are often faced with perturbations called disruptions (bad weather conditions, technical failures, congestion, crew illness…), planning for better performance under uncertainty is an additional dimension to the complexity of the problem. Our main focus is to develop better schedules that are less sensitive to perturbations and, when severe disruptions occur, are easier to recover. The former property is known as robustness and the latter is called recoverability. We start the thesis by addressing the problem of recovering a disrupted schedule. We present a general model, the constraint-specific recovery network, that encodes all feasible recovery schemes of any unit of the recovery problem. A unit is an aircraft, a crew member or a passenger and its recovery scheme is a new route, pairing or itinerary, respectively. We show how to model the Aircraft Recovery Problem (ARP) and the Passenger Recovery Problem (PRP), and provide computational results for both of them. Next, we present a general framework to solve problems subject to uncertainty: the Uncertainty Feature Optimization (UFO) framework, which implicitly embeds the uncertainty the problem is prone to. We show that UFO is a generalization of existing methods relying on explicit uncertainty models. Furthermore, we show that by implicitly considering uncertainty, we not only save the effort of modeling an explicit uncertainty set: we also protect against possible errors in its modeling. We then show that combining existing methods using explicit uncertainty characterization with UFO leads to more stable solutions with respect to changes in the noise's nature. We illustrate these concepts with extensive simulations on the Multi-Dimensional Knapsack Problem (MDKP). We then apply the UFO to airline scheduling. First, we study how robustness is defined in airline scheduling and then compare robustness of UFO models against existing models in the literature. We observe that the performance of the solutions closely depend on the way the performance is evaluated. UFO solutions seem to perform well globally, but models using explicit uncertainty have a better potential when focusing on a specific metric. Finally, we study the recoverability of UFO solutions with respect to the recovery algorithm we develop. Computational results on a European airline show that UFO solutions are able to significantly reduce recovery costs.

The personal positioning and navigation became a very challenging topic in our dynamic time. The urban canyons and particularly indoors represent the most difficult areas for personal navigation problematic. Problems like disturbed satellite signals make the positioning impossible indoors. Recently developed systems for indoor positioning do not assure the necessary positioning accuracy or are very expensive. Our concept stands for a fully autonomous positioning and navigation process. That is, a method that does not rely on the reception of external information, like satellite or terrestrial signals. Therefore, this research is based on the use of inertial measurements of the human walk and the map database which contains the graphic representation of the elements of the building, created by applying the link-node model. Using this reduced set of information the task is to develop methodology, based on the interaction of the data from both sources, to assure reliable positioning and navigation process. This research is divided in three parts. The first part consists in the development of a methodology for initial localization of the person indoors. The problem to solve is to localize the person in the building. Consider a person equipped with a system which contains set of inertial sensors and map database of the building. Speed, turn rate and barometric altitude are measured and time-stamped on each step of the person. A pre-processing phase uses these raw measurements in order to construct a polyline, thus representing user's trajectory. In the localization approach central place takes the association of the user's trajectory with the graph representation of the building, process known as map-matching. The solution is based on statistical method where the determination of the user's position is entirely represented by its probability density function (PDF) in the frame of Bayesian inference. Initial localization determines the edge of the graph occupied by the person. The second part aims at continuous localization, where user's position is estimated on every step. Besides the application of the classical map-matching techniques, two new methods are developed. Both rely on the similarity of the geometry of the trajectory and the elements of the graph. The first is based on the Bayesian inference, where the estimation is computed considering the walked distance and azimuth. The second method represents a new application of the Fréchet distance as degree of similarity between two polylines. The third part is pointed at the pedestrian guidance. Once the user's position is known it is easy to compute the path to his destination and to give him directions. The problem is to assure continuance of the process of navigation in the case when the person has lost his path. In that case the solution consists in either giving instructions to the user to go back on the path or computation of a new path from the actual position of the user to his destination. Based on that methodology, algorithms for initial localization, continuous localization, and guidance were created. Numerous tests with the participation of several persons have been provided in order to validate the algorithms and to show their performance, robustness and limits.

In this thesis, we focus on standard classes of problems in numerical optimization: unconstrained nonlinear optimization as well as systems of nonlinear equations. More precisely, we consider two types of unconstrained nonlinear optimization problems. On the one hand, we are interested in solving problems whose second derivatives matrix is singular at a local minimum. On the other hand, we focus on the identification of a global minimum of problems which present several local minima. The increasing use of simulation tools in real applications requires solving more and more complicated problems of these classes. The main goal of this thesis is the development of efficient numerical methods, based on trust-region and filter frameworks, able to find the solution of such problems in a limited number of function evaluations. Indeed, the algorithmic developments we present have been motivated by real transportation applications in which the objective function is usually cumbersome to evaluate. The specific nonlinear optimization problems mentioned above are encountered in the estimation of discrete choice models while systems of nonlinear equations have to be solved in the context of Dynamic Traffic Management Systems (DTMS). We also dedicate a part of this dissertation to the challenging task of human behavior modeling in the context of DTMS. First we propose a new trust-region algorithm and a new filter algorithm to solve singular unconstrained nonlinear problems. A characterization of the singularity at a local minimum is described and we present an iterative procedure which allows to identify a singularity in the objective function during the execution of the optimization algorithm. Our trust-region based algorithms make use of information on the singularity by adopting a penalty approach. Numerical results provide evidence that our approaches require less function evaluations to solve singular problems compared to classical trust-region algorithms from the literature. The CPU time to find a solution is also significantly decreased when the problem is singular. Second we present a new heuristic designed for nonlinear global optimization, based on the variable neighborhood search from discrete optimization within which we use a trust-region algorithm from nonlinear optimization as local search procedure. The algorithm we propose is able to prematurely stop the local search as soon as it does not look promising. The neighborhoods and the neighbors selection are based on information about the curvature of the objective function. Intensive numerical tests illustrate that our method is able to significantly reduce the average number of function evaluations compared to existing heuristics in the literature of nonlinear global optimization. Important improvements are also obtained in terms of success rate as well as CPU time. Third we design a new secant method for systems of nonlinear equations. The proposed algorithm uses a population of previous iterates and the linear model of the system is calibrated using a least squares approach. We also propose two globalization techniques for quasi-Newton methods in this context, namely a linesearch framework and a linesearch-filter approach. Our algorithm exhibits a faster convergence as well as a better robustness compared to secant methods from the literature. Globalization strategies are shown to highly increase the robustness of considered secant methods. Moreover, the combination of our algorithm with these strategies gives rise to an algorithmic method which is competitive with Newton-Krylov methods both in terms of robustness and efficiency. Fourth we present a real application of discrete choice models in the context of DTMS. The models are designed to capture the response of Swiss drivers to real-time traffic information. We are interested in drivers' decisions in terms of both route and mode choices when traffic information is available before the trip starts while we focus on route choice when traffic information is available during the trip. The "en-route" model is a mixture of binary logit model with panel data while "pre-trip" models are nested logit models. These models are estimated with the BIOGEME software developed by Bierlaire (2003). Estimation results are deeply analyzed and discussed, and models are implemented in a simulator which predicts drivers' behavior in specific scenarii. We conclude this thesis by a review of the main results and we make some comments about promising tracks for future research.

Intelligent Transportation Systems (ITS) have triggered important research activities in the context of behavioral dynamics. Several new models and simulators for driving and travel behaviors, along with new integrated systems to manage various elements of ITS, have been proposed in the past decades. In this context, less attention has been given to pedestrian modeling and simulation. In 2001, the first international conference on Pedestrian and Evacuation Dynamics took place in Duisburg, Germany, showing the recent, growing interest in pedestrian simulation and modeling in the scientific community. The ability of predicting the movements of pedestrians is valuable indeed in many contexts. Architects are interested in understanding how individuals move into buildings to find out optimality criteria for space design. Transport engineers face the problem of integration of transportation facilities, with particular emphasis on safety issues for pedestrians. Recent tragic events have increased the interest for automatic video surveillance systems, able to monitoring pedestrian flows in public spaces, throwing alarms when abnormal behaviors occur. In this spirit, it is important to define mathematical models based on specific (and context-dependent) behavioral assumptions, tested by means of proper statistical methods. Data collection for pedestrian dynamics is particularly difficult and few models presented in literature have been calibrated and validated on real datasets. Pedestrian behavior can be modelled at various scales. This work addresses the problem of pedestrian walking behavior modeling, interpreting the walking process as a sequence of choices over time. People are assumed to be rational decision makers. They are involved in the process of choosing their next position in the surrounding space, as a function of their kinematic characteristics and reacting to the presence of other individuals. We choose a mathematical framework based on discrete choice analysis, which provides a set of well founded econometric tools to model disaggregate phenomena. The pedestrian model is applied in a computer vision application, namely detection and tracking of pedestrians in video sequences. A methodology to integrate behavioral and image-based information is proposed. The result of this approach is a dynamic detection of the individuals in the video sequence. We do not make a clear cut between detection and tracking, which are rather thought as inter-operating procedures, in order to generate a set of hypothetical pedestrian trajectories, evaluated with the proposed model, exploiting both dynamic and behavioral information. The main advantage applying such methodology is given by the fact that the standard target detection/ recognition step is bypassed, reducing the complexity of the system, with a consistent gain in computational time. On the other hand, the price to pay as a consequence for the simple initialization procedure is the overestimation of the number of targets. In order to reduce the bias in the targets' number estimation, a comparative study between different approaches, based on clustering techniques, is proposed.

We have developed a new derivative-free algorithm based on Radial Basis Functions (RBFs). Derivative-free optimization is an active field of research and several algorithms have been proposed recently. Problems of this nature in the industrial setting are quite frequent. The reason is that in a number of applications the optimization process contains simulation packages which are treated as black boxes. The development of our own algorithm was originally motivated by an application in biomedical imaging: the medical image registration problem. The particular characteristics of this problem have incited us to develop a new optimization algorithm based on trust-region methods. However it has been designed to be generic and to be applied to a wide range of problems. The main originality of our approach is the use of RBFs to build the models. In particular we have adapted the existing theory based on quadratic models to our own models and developed new procedures especially designed for models based on RBFs. We have tested our algorithm called BOOSTERS against state-of-the-art methods (UOBYQA, NEWUOA, DFO). On the medical image registration problem, BOOSTERS appears to be the method of choice. The tests on problems from the CUTEr collection show that BOOSTERS is comparable to, but not better than other methods on small problems (size 2-20). It is performing very well for medium size problems (20-80). Moreover, it is able to solve problems of dimension 200, which is considered very large in derivative-free optimization. We have also developed a new class of algorithms combining the robustness of derivative-free algorithms with the faster rate of convergence characterizing Newtonlike-methods. In fact, they define a new class of algorithms lying between derivative-free optimization and quasi-Newton methods. These algorithms are built on the skeleton of our derivative-free algorithm but they can incorporate the gradient when it is available. They can be interpreted as a way of doping derivative-free algorithms with derivatives. If the derivatives are available at each iteration, then our method can be seen as an alternative to quasi-Newton methods. At the opposite, if the derivatives are never evaluated, then the algorithm is totally similar to BOOSTERS. It is a very interesting alternative to existing methods for problems whose objective function is expensive to evaluate and when the derivatives are not available. In this situation, the gradient can be approximated by finite differences and its costs corresponds to n additional function evaluations assuming that Rn is the domain of definition of the objective function. We have compared our method with CFSQP and BTRA, two gradient-based algorithms, and the results show that our doped method performs best. We have also a theoretical analysis of the medical image registration problem based on maximization of mutual information. Most of the current research in this field is concentrated on registration based on nonlinear image transformation. However, little attention has been paid to the theoretical properties of the optimization problem. In our analysis, we focus on the continuity and the differentiability of the objective function. We show in particular that performing a registration without extension of the reference image may lead to discontinuities in the objective function. But we demonstrate that, under some mild assumptions, the function is differentiable almost everywhere. Our analysis is important from an optimization point of view and conditions the choice of a solver. The usual practice is to use generic optimization packages without worrying about the differentiability of the objective function. But the use of gradient-based methods when the objective function is not differentiable may result in poor performance or even in absence of convergence. One of our objectives with this analysis is also that practitioners become aware of these problems and to propose them new algorithms having a potential interest for their applications.

Two of the most basic problems encountered in numerical optimization are least-squares problems and systems of nonlinear equations. The use of more and more complex simulation tools on high performance computers requires solving problems involving an increasingly large number of variables. The main thrust of this thesis the design of new algorithmic methods for solving large-scale instances of these two problems. Although they are relevant in many different applications, we concentrate specifically on real applications encountered in the context of Intelligent Transportation Systems to illustrate their performances. First we propose a new approach for the estimation and prediction of OriginDestination tables. This problem is usually solved using a Kalman filter approach, which refers to both formulation and resolution algorithm. We prefer to consider a explicit least-squares formulation. It offers convenient and flexible algorithms especially designed to solve largescale problems. Numerical results provide evidence that this approach requires significantly less computation effort than the Kalman filter algorithm. Moreover it allows to consider larger problems, likely to occur in real applications. Second a new class of quasi-Newton methods for solving systems of nonlinear equations is presented. The main idea is to generalize classical methods by building a model using more than two previous iterates. We use a least-squares approach to calibrate this model, as exact interpolation requires a fixed number of iterates, and may be numerically problematic. Based on classical assumptions we give a proof of local convergence of this class of methods. Computational comparisons with standard quasi-Newton methods highlight substantial improvements in terms of robustness and number of function evaluations. We derive from this class of methods a matrix-free algorithm designed to solve large-scale systems of nonlinear equations without assuming any particular structure on the problems. We have successfully tried out the method on problems with up to one million variables. Computational experiments on standard problems show that this algorithm outperforms classical large-scale quasi-Newton methods in terms of efficiency and robustness. Moreover, its numerical performances are similar to Newton-Krylov methods, currently considered as the best to solve large-scale systems of equations. In addition, we provide numerical evidence of the superiority of our method for solving noisy systems of nonlinear equations. This method is then applied to the consistent anticipatory route guidance generation. Route guidance refers to information provided to travelers in an attempt to facilitate their decisions relative to departure time, travel mode and route. We are specifically interested in consistent anticipatory route guidance, in which real-time traffic measurements are used to make short-term predictions, involving complex simulation tools, of future traffic conditions. These predictions are the basis of the guidance information that is provided to users. By consistent, we mean that the anticipated traffic conditions used to generate the guidance must be similar to the traffic conditions that the travelers are going to experience on the network. The problem is tricky because, contrarily to weather forecast where the real system under consideration is not affected by information provision, the very fact of providing travel information may modify the future traffic conditions and, therefore, invalidate the prediction that has been used to generate it. Bottom (2000) has proposed a general fixed point formulation of this problem with the following characteristics. First, as guidance generation involves considerable amounts of computation, this fixed point problem must be solved quickly and accurately enough for the results to be timely and of use to drivers. Secondly the unavailability of a closed-form objective function and the presence of noise due to the use of simulation tools prevent from using classical algorithms. A number of simulation experiments based on two system software including DynaMIT a state-of-the-art, real-time computer system for traffic estimation and prediction, developed at the Intelligent Transportation Systems Program of the Massachusetts Institute of Technology (MIT), have been run. These numerical results underline the good behavior of our large-scale method compared to classical fixed point methods for solving the consistent anticipatory route guidance problem. We close with some comments about future promising directions of research.