In this study, a comprehensive set of transit, intermodal and multimodal assignment models (FAST-TrIPs) is developed for transportation planning and operations purposes. The core part of the models is a schedule-based transit assignment with capacity constraint and boarding priority. The problem is defined to model the system performance dynamically by taking into account the scheduled transit service and to model user behavior more realistically by taking into account capacity of transit vehicles and boarding priority for passengers arriving early to a stop or a transfer point. An optimization model is proposed for both deterministic and stochastic models, which includes a penalty term in the objective function to model the boarding priority constraint. The stochastic model is proposed based on logit route choice with flexibility on the level of stochasticity in route choice. Optimality conditions show that the models are consistent with network equilibrium and user behavior. An extension of the optimization models is proposed for multimodal assignment problem, in which the transit and auto networks interact dynamically. To solve the proposed models, since the penalty term is non-linear and makes the model an asymmetric nonlinear optimization model with side constraints, a simulation-based approach is developed. The solution method incorporates the path assignment models and a mesoscopic transit passenger simulation in conjunction with Dynamic Traffic Assignment (DTA) models. The simulation model can capture detailed activities of transit passengers and determines the nonlinear penalty explicitly by reporting passengers' failure to board experience. Therefore, the main problem can be solved iteratively, by solving a relaxed problem and simulating the transit network in each iteration, until the convergence criterion is met. The relaxed problem is a path generation model and can be either a shortest/least-cost path or a logit-based hyperpath in the schedule-based transit network. An efficient set of path models are developed using Google's General Transit Feed Specification (GTFS) files, taking into account the transit network hierarchy for computational efficiency of the model. A multimodal assignment model is also developed by integration of the proposed transit assignment model with DTA models. The model is based on simulation and is able to capture the effect of transit and auto mode on each other through an iterative solution method and feedback loop from the transit assignment model to the DTA models. In the multimodal assignment model, more realistic transit vehicle trajectories are generated in the DTA models and are used for assigning transit passengers to transit vehicles. In an application of the multimodal assignment, intermodal tours are modeled considering the timing of auto trips and transit connections, the schedule-based transit network, and the constraint on park-n-ride choice in a tour. The model can simulate the transit, auto, and intermodal tours together with high resolution and realistic user behavior.

Schedule-based transit assignment models have been studied extensively from 2000, considering more time-dependent transit passenger behavior associated with the transit schedule. Currently, transit schedule information is more easily accessed using new telecommunications systems, such as mobile devices and the internet. One critical example of information sharing is Google's General Transit Feed Specification (GTFS). The information of the schedule per se, however, is not enough to explain the transit passenger's behavior, especially in a congested transit system. Regarding the congestion issues on a transit system, numerous researches have studied a transit schedule network (Nguyen et al., 2001; Nuzzolo et al., 2001; Poon et al., 2004; Hamdouch and Lawphonpanich, 2008, 2010).Along the stream toward understanding transit passenger behavior in the capacitated transit schedule network, we propose solution models for solving the deterministic and stochastic user equilibrium (SUE) problems on a capacitated transit schedule network. Nguyen et al. (2001) introduced how the capacitated user equilibrium (UE) on a transit schedule network is different from the auto user equilibrium. For the foundation of the study, we utilize the link-based and time-expanded (LBTE) transit schedule network introduced by Noh et al. (2012a) which effectively captures turning movements like transfers easily as well as maintaining the efficient size of a schedule-based network. In the LBTE transit network, time points are assigned to each link connecting two stops by each run (or route). Utilizing the "link-based" structure, a link-based shortest path (LBSP) and hyperpath search (LBHP) models (Noh et al., 2012a) are introduced. Especially, the hyperpath employs a log-sum weighting function for incorporating multiple schedule alternatives at each stop node considering passenger's stochastic behavior. One distinctive transit passenger behavior over a congested transit system is a first-in-first-out (FIFO) priority on boarding. A passenger already on board has the higher priority than passengers who are about to boarding, and the passengers arriving earlier at a stop will have higher priority than the passengers arriving later at the stop. To consider the capacitated UE considering the relation between the FIFO boarding priority and vehicle capacity constraint, we apply a "soft-capacity" cost (Nguyen et al., 2001). This soft capacity cost function allows some violation of the predefined vehicle capacity, but the violation will be penalized and affect the cost of the path in the next iteration. The penalty of the soft capacity cost function allows not to assigning passengers on the alternatives having the lower priority of boarding, which finally leads to the solution of the capacitated transit deterministic user equilibrium (DUE) or SUE problems. For the main transit assignment models, we proposed path- and hyperpath-based methods and a self-adaptive method considering deterministic and stochastic passenger behaviors. First, we developed the hyperpath-based assignment method by Noh et al. (2012b). For the FIFO transit passenger behavior, typically accompanying asymmetric (non-separable) cost relation, we also introduce a diagonalization technique (Sheffi, 1985) with the method of successive average (MSA) assignment technique. As expecting a better performance, second, we introduced the path-based assignment models using gradient projection. For the FIFO passenger behavior on boarding, we considered the same diagonalization approach used in the hyperpath-based assignment model and a full-Hessian scaling matrix in the gradient projection. By utilizing a full path set for each O-D pair, a better performance is guaranteed with the path-based model but the diagonalization technique may result in longer iterations. For improving the diagonalization steps, third, we explored several other possible methods. Above all, we proposed the better initial solution (BIS) model which assigns the initial flows on the priority path over congested links and also maintains feasible flows below the capacity constraint. On the other hand, we also added two additional assignment models to improve the diagonalization technique. One utilizes a full Hessian scaling matrix in the proposed path-based assignment model instead of diagonalization and the other is the self-adaptive gradient projection (SAGP) model introduced by Chen et al. (2012) which does not require a scaling matrix by optimizing the step-size in the path-based projection model. For improving the SAGP model, we modified the SAGP model. First, we applied the SAGP at a disaggregate level for each O-D pair as expecting a compact set of path alternatives limited by each O-D pair, called disaggregate self-adaptive gradient projection (DSAGP). Second, we applied a type of diagonalization technique in the SAGP model by maintaining the residual capacities for the estimated flows in the next iteration. Beyond just a single model development, the proposed transit assignment models not only showed various possibilities of the transit assignment, but also showed which model is more efficient and practical in terms of a real application. A computational model structure using the proposed models was mainly designed for an effective model development by sharing numerous components as well as maintaining the efficient data structure. The nine combination models based on the proposed three main models (hyperpath- and path-based and DSAGP assignment models) and the efficient BIS technique for solving the problems were tested and analyzed on a sample network and a partial Sacramento regional transit network.

This PhD project is on the algorithmic aspects of synthesis planning and mass spectrometry; two separate chemical problems concerning the understanding of molecules and how these behave. Part I: In synthesis planning, the goal is to synthesize a target molecule from available starting materials, possibly optimizing costs such as price or environmental impact of the process. Current algorithmic approaches to synthesis planning are usually based on selecting a bond set and finding a single good plan among those induced by it. We demonstrate that synthesis planning can be phrased as a combinatorial optimization problem on hypergraphs, not necessarily using a pre-defined bond set. For this, individual synthesis plans are modeled as directed hyperpaths embedded in a hypergraph of reactions (HoR) representing the chemistry of interest. As a consequence, application of a know polynomial time algorithm to find the K shortest hyperpaths yields the K best synthesis plans for a given target molecule. To this end, classical quality measures are discussed. Having K good plans to choose from has several benefits: It makes the synthesis planning process much more robust when in later stages adding further chemical details, it allows one to combine several notions of cost, and it provides a way to deal with imprecise yield estimates. An empirical study of our method illustrates the limitations of what a chemist can expect is feasible to compute, as well as the practical value of our method for cases where yield estimates are imprecise or unknown. To illustrate the realism of the approach, synthesis plans from our abstraction level are compared with detailed chemical synthesis plans from the literature. For this, a synthesis plan for Wieland-Miescher ketone and a synthesis plan for lysergic acid are used. In addition, equivalence of our structural definition of a hyperpath and two definitions from the hypergraph literature is shown. Part II: Mass spectrometry is an analytic technique for characterizing molecules and molecular mixtures, by gaining knowledge of their structure and composition from the way they fragment. In a mass spectrometer, molecules or molecular mixtures are ionized and fragmented, and the abundances of the different fragment masses are measured, resulting in so-called mass spectra. We suggest a new road map improving the current state-of-the art in computational methods for mass spectrometry. The main focus is on increasing the chemical realism of the modeling of the fragmentation process. Two core ingredients for this are i) describing the individual fragmentation reactions via graph transformation rules and ii) expressing the dynamics of the system via reaction rates and quasi-equilibrium theory. Graph transformation rules are used both for specifying the possible core fragmentation reactions, and for characterizing the reaction sites when learning values for the rates. We believe that this model describes chemical mechanisms more accurately than previous ones, and that this can lead to both better spectrum prediction and more explanatory power. Our modeling of system dynamics also allows better separation of instrument dependent and instrument independent parameters of the model.

京都大学 / 0048 / 新制・課程博士 / 博士(工学) / 甲第21361号 / 工博第4520号 / 新制||工||1704(附属図書館) / 京都大学大学院工学研究科都市社会工学専攻 / (主査)教授 山田 忠史, 教授 藤井 聡, 准教授 SCHMOECKER,Jan-Dirk / 学位規則第4条第1項該当 / Doctor of Philosophy (Engineering) / Kyoto University / DFAM

Classical planning is the problem of nding a sequence of actions that take an agent from an initial state to a desired goal situation, assuming deter- ministic outcomes for actions and perfect information. Satis cing planning seeks to quickly nd low-cost solutions with no guarantees of optimality. The most e ective approach for satis cing planning has proved to be heuristic search using non-admissible heuristics. In this thesis, we introduce several such heuristics that are able to take into account costs on actions, and there- fore try to minimize the more general metric of cost, rather than length, of plans, and investigate their properties and performance. In addition, we show how the problem of planning with soft goals can be compiled into a classical planning problem with costs, a setting in which cost-sensitive heuristics such as those presented here are essential. / La plani caci on cl asica es el problema que consiste en hallar una secuencia de acciones que lleven a un agente desde un estado inicial a un objetivo, asum- iendo resultados determin sticos e informaci on completa. La plani caci on \satis cing" busca encontrar una soluci on de bajo coste, sin garant as de op- timalidad. La b usqueda heur stica guiada por heur sticas no admisibles es el enfoque que ha tenido mas exito. Esta tesis presenta varias heur sticas de ese g enero que consideran costes en las acciones, y por lo tanto encuentran soluciones que minimizan el coste, en lugar de la longitud del plan. Adem as, demostramos que el problema de plani caci on con \soft goals", u objetivos opcionales, se puede reducir a un problema de plani caci on clasica con costes en las acciones, escenario en el que heur sticas sensibles a costes, tal como las aqu presentadas, son esenciales.