working paper

An Alternative Method to Estimate Balancing Factors for the Disaggregation of OD Matrices

Abstract

The solution algorithms for the family of flow distribution problems, which include (1) the trip distribution problem of travel forecasting, (2) the OD estimation from link counts problem, and (3) the trip matrix disaggregation problem, are usually based on the Maximum Entropy (ME) principle. ME-based optimization problems are hard to solve directly by optimization techniques due to the complexity of the objective function. Thus, in practice, iterative procedures are used to find approximate solutions. These procedures, however, cannot be easily applied if additional constraints are needed to be included in the problem. In this paper a new approach for balancing trip matrices with application in trip matrix disaggregation is introduced. The concept of generating the most similar distribution (MSD) instead of the Most Probable Distribution of Maximum Entropy principle is the basis of this approach. The goal of MSD is to minimize the deviation from the initial trip distribution, while satisfying additional constraints. This concept can be formulated in different ways. Two MSD-based objective functions have been introduced in this paper to replace the ME-based objective function. One is the Sum of Squared Deviations MSD (SSD-MSD), and the other is Minimax-MSD. While SSD-MSD puts more emphasis on maintaining the base year trip shares as a whole, Minimax-MSD puts more emphasis on maintaining the share of each individual element in the trip table. The main advantage of replacing the entropy-based objective functions with any of these functions is that the resulting problems can include additional constraints and still be readily solved by standard optimization engines. In addition, these objective functions could produce more meaningful results than entropy-based functions in regional transportation planning studies, as shown in the case study and some of the examples in the paper. Several examples and a case study of the California Statewide Freight Forecasting Model (CSFFM) are presented to demonstrate the merits of using MSD-based formulations.

working paper

Stochastic Dynamic Itinerary Interception Refueling Location Problem with Queue Delay for Electric Taxi Charging Stations

Abstract

A new facility location model and a solution algorithm are proposed that feature 1) itinerary-interception instead of flow-interception; 2) stochastic demand as dynamic service requests; and 3) queueing delay. These features are essential to analyze battery-powered electric shared-ride taxis operating in a connected, centralized dispatch manner. The model and solution method are based on a bi-level, simulation-optimization framework that combines an upper level multiple-server allocation model with queueing delay and a lower level dispatch simulation based on earlier work by Jung and Jayakrishnan. The solution algorithm is tested on a fleet of 600 shared-taxis in Seoul, Korea, spanning 603 km2, a budget of 100 charging stations, and up to 22 candidate charging locations, against a benchmark “naïve” genetic algorithm that does not consider cyclic interactions between the taxi charging demand and the charger allocations with queue delay. Results show not only that the proposed model is capable of locating charging stations with stochastic dynamic itinerary-interception and queue delay, butt that the bi-level solution method improves upon the benchmark algorithm in terms of realized queue delay, total time of operation of taxi service, and service request rejections. Furthermore, we show how much additional benefit in level of service is possible in the upper-bound scenario when the number of charging stations approaches infinity.

Phd Dissertation

The development and evaluation of a highly-resolved California electricity market model to characterize the temporal and spatial grid, environmental, and economic impacts of electric vehicles

Abstract

Drastic changes need to occur in the electricity generation and transportation sectors in order to address environmental concerns that have attracted attention in recent years. These concerns, combined with increasing energy prices, have led to elevated interest in alternative, and low to non-carbon technologies in both sectors from both researchers and policymakers. In the state of California, integration of renewable resources, and switching to more environmental-friendly transportation options, have been mandated by stringent environmental regulations such as AB 32, AB 118, and RPS goals. A spatially and temporally resolved resource dispatch model is developed that simulates the operations of an electricity market while taking into account all the physical constraints associated with various components of an electricity grid such as transmission system constraints. Multiple modules are also developed to provide inputs to the model and also determine the interaction between electricity generation and transportation sectors. This dispatch model and its modules are used to assess a selected set of future transportation and electricity generation scenarios. These scenarios include various dispatch strategies, integration of renewables, and deploying plug-in electric vehicles. The results show that with appropriate planning, the generation, transmission, and distribution sectors will be able to accommodate a high penetration of plug-in vehicles, and they will result in an overall reduction in criteria pollutant and greenhouse gas emissions. With vehicle smart charging, the need for planning in the generation sector is minimized and the installed generators will be able to handle the extra load caused by the vehicles. Different dispatch strategies are developed and results indicate that the best approach to reduce emissions while keeping the system’s costs at acceptable levels is a combination of economic and environmental dispatch strategies. This strategy can also be used to dispatch renewable resources as a part of the market instead of using the current must-take strategy. The methodology and the tools developed provide a means to examine various aspects of future scenarios and their impacts on different sectors, and can be used for decision making and planning purposes.

Phd Dissertation

Online Advertising: A Large Scale Computing Perspective

Abstract

Online advertising is emerging as a primary industry for major computer science companies such as Facebook, Google, Microsoft and Yahoo!. From a computing perspective, we face challenges to match the best ads to suitable users within fast enough response times on the massive industrial Petabyte scale of data. In this thesis, centered on computational problems related to online ad problems, the main contributions are: to provide a new statistical model for ad response prediction; a new parallel computing algorithm for model inference; a new optimization method in an online stochastic environment; and exploration and exploitation for ad selection in time-varying dynamic systems. First, we introduce a Bayesian Regression Model for click through rate prediction, and develop and parallelize learning and inference algorithms in the distributed Hadoop Map-Reduce framework. Then, we propose a Multi-Core Gibbs Sampling. Our exact parallel inference achieves near linear speedup in the complex statistical models on 1.8 million news articles from over 20 years of the New York Times. Moreover, we develop a voted Dual Average method for online classification, derive the training and generalization error bounds, and achieve state-of-the-art performance in parsing reranking. Finally, we discuss the exploration and exploitation in a more realistic scenario under a time-varying environment. We introduce different discount factors (e.g.exponential decay) according to the underlying dynamics; and consequently our algorithm is able to trade-off exploration and exploitation adaptively.

Phd Dissertation

Essays on econometric methodology and application

Publication Date

June 14, 2013

Author(s)

Abstract

This dissertation is composed of three chapters on estimation of vehicle choice and utilization models, simulated likelihood estimation, and Bayesian non-parametric additive methods for neighborhood effect models. The first chapter exploits differences in fuel efficiency between hybrid vehicles and their gasoline counterparts to investigate two behavioral questions relating to fuel economy standards: how car buyers value fuel economy (the energy paradox) and whether improved fuel efficiency increases travel (the rebound effect). Emphasis is placed on handling methodological and data issues that are typically ignored in prior studies, such as partially observed choice, endogeneity, and measurement error. Estimates of the rebound effect and consumer valuation of fuel economy remain imprecise despite the use of the most detailed household level data available and sound methodology to handle limitations with these data. The inability to precisely estimate these important policy questions suggests it is a worthwhile endeavor to obtain reliable, detailed data on household vehicles. The following chapter (joint with Ivan Jeliazkov) presents techniques, based on Markov chain Monte Carlo (MCMC) theory, for construction of the likelihood function in a broad class of hierarchical models where direct evaluation of the likelihood function is not possible. We review existing estimators, introduce new MCMC estimators, and examine their performance in applications to the Poisson-log normal and mixed logit models. The MCMC techniques outperform existing methods in both settings, with the existing methods performing especially poorly in the Poisson-log normal case. The final chapter applies Bayesian semiparametric additive methods to a neighborhood effects model. The baseline model assumes all covariates enter linearly, whereas the approach in this paper allows for flexible functional forms. An efficient Markov chain Monte Carlo (MCMC) algorithm that exploits the properties of banded matrices is proposed for estimation. The efficiency gains offered by the banded matrix algorithm are critical, as they permit the estimation of applications with large sample sizes. The model and estimation methodology are used to examine foreclosure contagion in California. The results reveal the impact of neighborhood effects on foreclosure rates as nonlinear, where the relationship resembles a tipping point phenomenon.

Phd Dissertation

Choices and constraints : gender differences in travel behavior

Publication Date

June 29, 2013

Author(s)

Abstract

The purpose of my dissertation is to explore how gender interacts with other factors such as personal attitudes, earning power, household structure, and the built environment to influence travel behavior, with a focus on whether these factors strengthen or relieve the constraints women face when making travel choices. In this context, my dissertation is organized around three separate case studies in California that rely on various discrete choice econometric models. Results from my first case study indicate that chauffeuring trips in two-adult households with children are intensely gendered, and women bear most of the chauffeuring burden. It is partly because women’s income earning potential is generally lower than that of their male partners. However, living in neighborhoods with access to bus stop and with less single-family housing can reduce this gender chauffeuring gap. It suggests that compact urban development and better bus service may yield social benefits that help alleviate women’s household burdens. In my second case study, I find that mothers are more likely to extend their greater concerns about traffic safety to their children, which in turn reduces the chance that their children will walk or bike to school. However, mothers bear most of the burden to chauffeur their children to school not because they worry more, but because chauffeuring children is still seen more as a mother’s responsibility. It suggests that interventions targeting an increase in children’s active commuting to school should focus on the concerns of mothers, especially as they relate to traffic characteristics. My findings in the third case study reveal that both environmental and safety concerns are associated with sustainable travel behavior, but the influence of safety concerns is more prominent and women have greater safety concerns. Moreover, proximity to transit service can increase sustainable travel behavior, but having higher safety concerns can totally offset this effect. For women with higher safety concerns, the reduction is even greater. It suggests that to encourage sustainable travel behavior, reducing personal safety concerns about transit use may be more effective than increasing public environmental awareness, especially for attracting potential female riders.

Phd Dissertation

Properties, Simulation, and Applications of Inter-Vehicle Communication Systems

Abstract

The growth of urban vehicle traffic generates serious transportation and environmental problems in most countries of the world. Intelligent transportation systems (ITS) are effective means to solve basic traffic problems, such as driving safety, road congestion, disaster supplies, emissions, etc. Inter-vehicle communication (IVC) system is one of the most important components of ITS. In recent years, the rapid development of information technologies leads a revolution in IVC, enabling IVC be a powerful multifunctional system. However, there exist numerous challenges for ITS studies. This dissertation is aimed to address three urgent and critical issues in IVC: efficiency of information exchanging among connected vehicles, simulation methods, and IVC applications. Information transmission efficiency, which can be measured by communication throughput or capacity, is a fundamental property of vehicular ad hoc networks. This dissertation theoretically analyzes communication throughputs, including broadcast and unicast communications, under discrete and continuous vehicular ad hoc networks (VANETs). We also examine influence of transmission range, interference ratio, market penetration rate of IVC-equipped vehicles, percentage of senders, and traffic waves on throughputs. Furthermore, we derive a theoretical formulation to calculate communication capacities under uniform traffic streams. And, an integer programming (IP) model is improved to explore capacities in general traffic, and a genetic algorithm is constructed to search the solutions efficiently. The second contribution of this dissertation is the development of a hybrid traffic simulation model to evaluate transportation systems incorporated with IVC technologies. As IVC-equipped vehicles are able to obtain more road information and they are controlled to pursue some objectives, they will behave differently from others, and transportation systems will become heterogeneous. This dissertation presents a hybrid traffic simulation model coupling microscopic and macroscopic models to address heterogeneity in transportation systems. In the model, equipped vehicles are regulated by a car-following model, while the other vehicles are described as continuous media with the Lighthill-Whitham-Richard (LWR) model. We analytically study the model on a single-lane road using a modified Godunov method. The hybrid model shows its potential of accurate wave propagation from individual vehicles to continuous traffic streams, and reversely; i.e., the model is capable of analyzing heterogeneous traffic. Moreover, consistency, stability and convergence of the hybrid model are carefully investigated. The model also shows the advancement of computational efficiency and control flexibility on traffic simulations. Finally, for IVC applications in environment, we propose a green driving strategy to smooth traffic flow and lower pollutant emissions and fuel consumption. In this dissertation, we study constant and dynamic green driving strategies based on inter-vehicle communications. Generally, speed limit control in successful strategies guarantee a vehicle’s speed profile be smooth while still following its leader during a relative long time period. A theoretical analysis of constant strategies demonstrates that optimal smoothing effects can be achieved when a speed limit is set to be close to but not smaller than average speed of traffic. We consider a dynamic strategy in which controlled vehicles share location and speed information based on a feedback control system. The influence of market penetration rate of equipped vehicles and communication delay on the strategy is also analyzed. Besides the development of the green driving strategy, we construct a green driving APP for smartphones on the Google Android platform and design a field experiment to check the feasibility of the strategy. The results are promising and support the advancements of IVC on reducing emissions and fuel consumption.

Phd Dissertation

The Perception-Intention-Adaptation (PIA) model : a theoretical framework for examining the effect of behavioral intention and neighborhood perception on travel behavior

Publication Date

June 14, 2013

Author(s)

Abstract

Recent research has indicated convincing evidence of a link between characteristics of the built environment and travel behavior. However, few land use – travel behavior studies include cognitive factors (such as attitudes, perceptions, and environmental norms) that have been found to affect travel mode choice in the social psychology literature. This dissertation develops and empirically tests a theoretical framework called the Perception-Intention-Adaptation (PIA) model that brings land use and attitude-behavior theory together in order to address gaps in the travel behavior literature. Following a detailed description of the PIA model, the dissertation is comprised of three empirical essays. The analyses in these essays are based on cross-sectional and panel data collected during the Expo Line Study, the first experimental-control, before-and-after evaluation of a rail transit investment in California. The first essay evaluates the predictive power of the core socio-psychological constructs of the PIA (attitudes, norms, and control beliefs) in combination with a comprehensive set of built environment and socio-economic measures. Regression models of transit use are used to analyze cross-sectional data obtained before the opening of the Exposition light rail line in Los Angeles. The analysis indicates that two PIA constructs, attitudes toward public transportation and concerns about personal safety, significantly improve the model fit and were robust predictors of transit use, independent of built environment factors. The second essay uses panel data collected before and after the opening of the Exposition light rail line to examine changes in travel behavior. A quasi-experimental approach with experimental (within ℗ư mile of an Expo station) and control (beyond ℗ư mile) households is used to evaluate the travel effects of the opening of the Expo line at the household level. The results show a statistically significant reduction in vehicle miles traveled (VMT) in the experimental group, though overall transit ridership and travel-related physical activity did not change significantly. The final essay uses the before and after opening panel data to examine socio-psychological aspects of travel behavior change in response to the Expo Line opening. Random effects models of transit use, car driver trips, and active travel trips all show that the socio-psychological constructs hypothesized in the PIA model do have a significant impact on travel behavior. In addition, cross-lagged models designed to examine the attitude-behavior relationship show an apparent causal pathway from attitudes to behavior for all three travel outcomes.

Phd Dissertation

Integration of Locational Decisions with the Household Activity Pattern Problem and Its Applications in Transportation Sustainability

Publication Date

June 14, 2013

Abstract

This dissertation focuses on the integration of the Household Activity Pattern Problem (HAPP) with various locational decisions considering both supply and demand sides. We present several methods to merge these two distinct areas—transportation infrastructure and travel demand procedures—into an integrated framework that has been previously exogenously linked by feedback or equilibrium processes. From the demand side, travel demand for non-primary activities is derived from the destination choices that a traveler makes that minimizes travel disutility within the context of considerations of daily scheduling and routing. From the supply side, the network decisions are determined as an integral function of travel demand rather than a given fixed OD matrix.

First, the Location Selection Problem for the Household Activity Pattern Problem (LSP-HAPP) is developed. LSP-HAPP extends the HAPP by adding the capability to make destination choices simultaneously with other travel decisions of household activity allocation, activity sequence, and departure time. Instead of giving a set of pre-fixed activity locations to visit, LSPxviii HAPP chooses the location for certain activity types given a set of candidate locations. A dynamic programming algorithm is adopted and further developed for LSP-HAPP in order to deal with the choices among a sizable number of candidate locations within the HAPP modeling structure. Potential applications of synthetic pattern generation based on LSP-HAPP formulation are also presented.

Second, the Location – Household Activity Pattern Problem (Location-HAPP), a facility location problem with full-day scheduling and routing considerations is developed. This is in the category of Location-Routing Problems (LRPs), where the decisions of facility location models are influenced by possible vehicle routings. Location-HAPP takes the set covering model as a location strategy, and HAPP as the scheduling and routing tool. The proposed formulation isolates each vehicle’s routing problem from those of other vehicles and from the master set covering problem. A modified column generation that uses a search method to find a column with a negative reduced price is proposed.

Third, the Network Design Problem is integrated with the Household Activity Pattern Problem (NDP-HAPP) as a bilevel optimization problem. The bilevel structure includes an upper level network design while the lower level includes a set of disaggregate household itinerary optimization problems, posed as HAPP or LSP-HAPP. The output of upper level NDP (level-ofservice of the transportation network) becomes input data for the lower level HAPP that generates travel demand which becomes the input for the NDP. This is advantageous over the conventional NDP that outputs the best set of links to invest in, given an assumed OD matrix. Because the proposed NDP-HAPP can output the same best set of links, a new OD matrix and a detailed temporal distribution of activity participation and travel are created. A decomposed xix heuristic solution algorithm that represents each decision makers’ rationale shows optimality gaps of as much as 5% compared to exact solutions when tested with small examples.

Utilizing the aforementioned models, two transportation sustainability studies are then conducted for the adoption of Alternative Fuel Vehicles (AFVs). The challenges in adopting AFVs are directly related to the transportation infrastructure problems since the initial AFV refueling locations will need to provide comparable convenient travel experience for the early adopters when compared to the already matured gasoline fuel based transportation infrastructure. This work demonstrates the significance of the integration between travel demand model and infrastructure problems, but also draws insightful policy measurements regarding AFV adoption.

The first application study attempts to measure the household inconvenience level of operating AFVs. Two different scenarios are examined from two behavioral assumptions – keeping currently reported pattern and minimizing the inconvenience cost through HAPPR or HAPPC. From these patterns, the personal or household inconvenience level is derived as compared to the original pattern, providing quantified data on how the public sector would compensate for the increases in travel disutility to ultimately encourage the attractiveness of AFVs.

From the supply side of the AFV infrastructure, Location-HAPP is applied to the incubation of the minimum refueling infrastructure required to support early adoption of Hydrogen Fuel Cell Vehicles (HFCVs). One of the early adoption communities targeted by auto manufacturers is chosen as the study area, and then three different values of accessibility are tested and measured in terms of tolerances to added travel time. Under optimal conditions, refueling trips are found to be toured with other activities. More importantly, there is evidence xx that excluding such vehicle-infrastructure interactions as well as routing and scheduling interactions can result in over-estimation of minimum facility requirement.

Phd Dissertation

Shared-ride Passenger Transportation Systems with Real-time Routing

Abstract

This dissertation describes a series of real-time vehicle routing problems with the associate optimization and simulation modeling for flexible passenger transport systems such as the High Coverage Point-to-Point Transit (HCPPT) and shared-taxi, which involve a sufficient number of deployed small vehicles with advanced information supply schemes to match real-time passenger demands and vehicle position for passenger transportation over large areas. HCPPT is an alternate design for mass passenger transport developed in recent years at the University of California at Irvine. The designs rely on transfer hubs, trunk route connections between the hubs where the vehicles are non-reroutable, and local areas around the hubs where the vehicles are reroutable. First, we relax the restriction in the existing heuristic rules of HCPPT, expecting to yield higher efficiency for general cases. Optimization schemes are proposed for both trunk and local vehicle routing problems to consider global optimality for large-scale problems. Significantly, the new algorithms allow globally optimal vehicle movements over multiple-hubs, unlike the earlier designs that allowed travel only to the adjacent hubs. This in turn ensures that the scheme has scalability in large areas and has design flexibility in adjusting the distances between hubs. Second, for an efficient and productive taxi system of the conventional kind, a design of shared-taxi operation is proposed, which also can be potentially used for local area operations in HCPPT. Three algorithms are developed and compared with different objective functions. Another contribution of this research is the development of a simulation platform targeting large-scale flexible point-to-point transit systems with various vehicle operation schemes. Traditionally, real-time DRT operations are simulated with commercial traffic simulators such as mesoscopic or microscopic simulation models, which is cumbersome because the available software were not designed for such real-time routed vehicle simulation, and also because they include details of less relevance to large-scale real-time Demand Responsive Transit (DRT) systems. The simulation studies in this research evaluate the vehicle routing algorithms through the proposed platform for Orange County, U.S.A. and Seoul, Korea. Finally, this thesis studies two large-scale fleet applications of Electric Vehicles (EV) as a future transportation alternative, as the hub locations which are part of the designs developed in this research are particularly suitable as energy replenishment nodes. Since EVs have a limited driving range and need to visit charging stations frequently, this part mainly focuses on the vehicle charge replenishing schedules in conjunction with passenger pickup and delivery schedules and measures the benefits from combining EVs and DRT fleets.