Civil & Environmental Engineering

Permanent URI for this communityhttp://hdl.handle.net/1903/2221

Browse

End date: 2009Subject: search.filters.subject.Operations Research

Search Results

Now showing 1 - 10 of 10
  • Thumbnail Image
    Item
    AN INTEGRATED TRAFFIC CONTROL SYSTEM FOR FREEWAY CORRIDORS UNDER NON-RECURRENT CONGESTION
    (2009) Liu, Yue; Chang, Gang-Len; Civil Engineering; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)
    This research has focused on developing an advanced dynamic corridor traffic control system that can assist responsible traffic professionals in generating effective control strategies for contending with non-recurrent congestion that often concurrently plagues both the freeway and arterial systems. The developed system features its hierarchical operating structure that consists of an integrated-level control and a local-level module for bottleneck management. The primary function of the integrated-level control is to maximize the capacity utilization of the entire corridor under incident conditions with concurrently implemented strategies over dynamically computed windows, including diversion control at critical off-ramps, on-ramp metering, and optimal arterial signal timings. The system development process starts with design of a set of innovative network formulations that can accurately and efficiently capture the operational characteristics of traffic flows in the entire corridor optimization process. Grounded on the proposed formulations for network flows, the second part of the system development process is to construct two integrated control models, where the base model is designed for a single-segment detour operation and the extended model is designated for general network applications. To efficiently explore the control effectiveness under different policy priorities between the target freeway and available detour routes, this study has further proposed a multi-objective control process for best managing the complex traffic conditions during incident operations. Due to the nonlinear nature of the proposed formulations and the concerns of computing efficiency, this study has also developed a GA-based heuristic along with a successive optimization process that can yield sufficiently reliable solutions for operating the proposed system in a real-time traffic environment. To evaluate the effectiveness and efficiency of the developed system, this study has conducted extensive numerical experiments with real-world cases. The experimental results have demonstrated that with the information generated from the proposed models, the responsible agency can effectively implement control strategies in a timely manner at all control points to substantially improve the efficiency of the corridor control operations. In view of potential spillback blockage due to detour operations, this study has further developed a local-level bottleneck management module with enhanced arterial flow formulations that can fully capture the complex interrelations between the overflow in each lane group and its impact on the neighboring lanes. As a supplemental component for corridor control, this module has been integrated with the optimization model to fine-tune the arterial signal timings and to prevent the queue spillback or blockages at off-ramps and intersections. The results of extensive numerical experiments have shown that the supplemental module is quite effective in producing local control strategies that can prevent the formation of intersection bottlenecks in the local arterial.
  • Thumbnail Image
    Item
    Optimal Number and Location of Bluetooth Sensors for Travel Time Data Collection in Networks
    (2009) Asudegi, Mona; Haghani, Ali; Civil Engineering; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)
    The importance of accurate prediction of travel time in transportation engineering is irrefutable. Travel time is highly used in traffic management and planning. The accuracy of travel time prediction relies on the accuracy of the travel time data. Various methods are being used in collecting travel time data. Recently, a new method in collecting travel time data is introduced that is called Bluetooth technology. In this method, a number of Bluetooth sensors are deployed over the traffic network that can detect the Bluetooth devices in the vehicles to determine the vehicles' travel time based on matching identification and time of identification of the same Bluetooth device at two consecutive sensors. The goal of this study is to find the optimal number and location of the Bluetooth sensors in a network in order to collect travel time data with a high reliability. Two formulations are proposed for modeling this problem. The formulations consider a new collection of reliability issues. Furthermore, the proposed formulations are able to solve the problem on large networks exactly. Moreover, various case studies of real world networks are conducted for both formulations and the results are compared.
  • Thumbnail Image
    Item
    Multiobjective Optimization Models for Distributing Biosolids to Reuse Fields
    (2008-01-24) Sahakij, Prawat; Gabriel, Steven A; Civil Engineering; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)
    The District of Columbia Water and Sewer Authority (DCWASA) operates the Blue Plains Wastewater Treatment Plant located in Washington, DC. It serves more than two million Washington Metro Area customers, and treats more than 330 million gallons a day of raw sewage from area jurisdictions, including Montgomery and Prince George's Counties in Maryland, and Fairfax and Loudoun Counties in Virginia. Each day, DCWASA produces approximately 1,200 tons of biosolids or byproducts of wastewater that have been treated to reduce pathogens and can be used as fertilizer for agricultural purposes. These generated biosolids require removal from the treatment facility and distribution to reuse fields located in Maryland and Virginia. In spite of the benefits of reuse, biosolids are generally considered by many as potentially malodorous. Recently, DCWASA has received complaints from the surrounding communities and needed to minimize biosolids odors. However, trying to minimize biosolids odors could result in costly treatment processes. Therefore, one needs to determine how to minimize the odors while at the same time minimizing the treatment costs. This compromise of balancing the competing objectives of odors and costs results in a two-objective or more generally, multiobjective optimization problem. In this dissertation, we develop multiobjective optimization models to simultaneously minimize biosolids odors as well as wastewater treatment process and biosolids distribution costs. A weighting method and constraint method were employed to find tradeoff, so called Pareto optimal, points between costs and odors. Schur's decomposition and special order set type two variables were used to approximate the product of two decision variables. A Dantzig-Wolfe decomposition technique was successfully applied to break apart and solve a large optimization model encountered in this dissertation. Using the Blue Plains advanced wastewater treatment plant as a case study, we find several Pareto optimal points between costs and odors where different treatments (e.g., lime addition) and biosolids distribution (e.g., to what reuse fields biosolids should be applied) strategies should be employed. In addition, to hedge the risk of equipment failures as well as for historical reasons, an on-site dewatering contractor has also been incorporated into the model. The optimal solutions indicate different uses of the contractor (e.g., percent flow assigned) when dewatering cost employed by DCWASA varies. This model can be used proactively by any typical advanced wastewater treatment plants to produce the least malodorous biosolids at minimal costs and to our knowledge, this is the first instance of such a model.
  • Thumbnail Image
    Item
    Topology Control and Pointing in Free Space Optical Networks
    (2007-12-05) Shim, Yohan; Gabriel, Steven A; Civil Engineering; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)
    Free space optical (FSO) communication provides functionalities that are different from fiber optic networks and omnidirectional RF wireless communications in that FSO is optical wireless (no infrastructure installation cost involving fibers) and is highly directional (no frequency interference). Moreover, its high-speed data transmission capability is an attractive solution to the first or last mile problem to bridge to current fiber optic network and is a preferable alternative to the low data rate directional point-to-point RF communications for inter-building wireless local area networks. FSO networking depends critically on pointing, acquisition and tracking techniques for rapidly and precisely establishing and maintaining optical wireless links between network nodes (physical reconfiguration), and uses topology reconfiguration algorithms for optimizing network performance in terms of network cost and congestion (logical reconfiguration). The physical and logical reconfiguration process is called Topology Control and can allow FSO networks to offer quality of service by quickly responding to various traffic demands of network users and by efficiently managing network connectivity. The overall objective of this thesis research is to develop a methodology for self-organized pointing along with the associated autonomous and precise pointing technique as well as heuristic optimization methods for Topology Control in bi-connected FSO ring networks, in which each network node has two FSO transceivers. This research provides a unique, autonomous, and precise pointing method using GPS and local angular sensors, which is applicable to both mobile and static nodes in FSO networking and directional point-to-point RF communications with precise tracking. Through medium (264 meter) and short (40 meter) range pointing experiments using an outdoor testbed on the University of Maryland campus in College Park, sub-milliradian pointing accuracy is presented. In addition, this research develops fast and accurate heuristic methods for autonomous logical reconfiguration of bi-connected ring network topologies as well as a formal optimality gap measure tested on an extensive set of problems. The heuristics are polynomial time algorithms for a congestion minimization problem at the network layer and for a multiobjective stochastic optimization of network cost and congestion at both the physical and network layers.
  • Thumbnail Image
    Item
    Air Express Network Design with Hub Sorting
    (2007-11-05) Ngamchai, Somnuk; Schonfeld, Paul M.; Civil Engineering; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)
    This dissertation examines an innovative strategic operation for next day air package delivery. The proposed system, in which some packages are sorted twice at two distinct hubs before arriving at their destinations, is investigated for its potential savings. A two-stage sorting operation is proposed and compared to the currently operated single-stage sorting operation. By considering the endogenous optimization of hub sorting and storage capacities, cost minimization models are developed for both operations and used for performance comparison. Two solution approaches are presented in this study, namely the Column Generation (CG) approach and the Genetic Algorithm (GA) approach. The first method is implemented to optimize the problem by means of linear programming (LP) relaxation, in which the resulting model is then embedded into a branch-and-bound approach to generate an integer solution. However, for solving realistic problem sizes, the model is intractable with the conventional time-space formulation. Therefore, a Genetic Algorithm is developed for solving a large-scale problem. The GA solution representation is classified into two parts, a grouping representation for hub assignment and an aircraft route representation for aircraft route cycles. Several genetic operators are specifically developed based on the problem characteristics to facilitate the search. After optimizing the solution, we compare not only the potential cost saving from the proposed system, but also the system's reliability based on its slack. To provide some insights on the effects of two-stage operation, several factors are explored such as the location of regional hubs, single and multiple two-stage routings and aircraft mix. Sensitivity analyses are conducted under different inputs, including different demand levels, aircraft operating costs and hub operating costs. Additional statistics on aircraft utilization, hub capacity utilization, circuity factor, average transfers per package, and system slack gain/loss by commodity, are analyzed to elucidate the changes in system characteristics.
  • Thumbnail Image
    Item
    MULTIOBJECTIVE OPTIMIZATION MODELS AND SOLUTION METHODS FOR PLANNING LAND DEVELOPMENT USING MINIMUM SPANNING TREES, LAGRANGIAN RELAXATION AND DECOMPOSITION TECHNIQUES
    (2005-08-04) Faria, Jose Alberto; Gabriel, Steven A; Civil Engineering; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)
    The land development problem is presented as the optimization of a weighted average of the objectives of three or more stakeholders, subject to develop within bounds residential, industrial and commercial areas that meet governmental goals. The work is broken into three main sections. First, a mixed integer formulation of the problem is presented along with an algorithm based on decomposition techniques that numerically has proven to outperform other solution methods. Second, a quadratic mixed integer programming formulation is presented including a compactness measure as applied to land development. Finally, to prevent the proliferation of sprawl a new measure of compactness that involves the use of the minimum spanning tree is embedded into a mixed integer programming formulation. Despite the exponential number of variables and constraints required to define the minimum spanning tree, this problem was solved using a hybrid algorithm developed in this research.
  • Thumbnail Image
    Item
    A Stochastic Equilibrium Model for the North American Natural Gas Market
    (2005-07-26) Zhuang, Jifang; Gabriel, Steven A.; Civil Engineering; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)
    This dissertation is an endeavor in the field of energy modeling for the North American natural gas market using a mixed complementarity formulation combined with the stochastic programming. The genesis of the stochastic equilibrium model presented in this dissertation is the deterministic market equilibrium model developed in [Gabriel, Kiet and Zhuang, 2005]. Based on some improvements that we made to this model including proving new existence and uniqueness results, we present a multistage stochastic equilibrium model with uncertain demand for the deregulated North American natural gas market using the recourse method of the stochastic programming. The market participants considered by the model are pipeline operators, producers, storage operators, peak gas operators, marketers and consumers. Pipeline operators are described with regulated tariffs but also involve "congestion pricing" as a mechanism to allocate scarce pipeline capacity. Marketers are modeled as Nash-Cournot players in sales to the residential and commercial sectors but price-takers in all other aspects. Consumers are represented by demand functions in the marketers' problem. Producers, storage operators and peak gas operators are price-takers consistent with perfect competition. Also, two types of the natural gas markets are included: the long-term and spot markets. Market participants make both high-level planning decisions (first-stage decisions) in the long-term market and daily operational decisions (recourse decisions) in the spot market subject to their engineering, resource and political constraints as well as market constraints on both the demand and the supply side, so as to simultaneously maximize their expected profits given others' decisions. The model is shown to be an instance of a mixed complementarity problem (MiCP) under minor conditions. The MiCP formulation is derived from applying the Karush-Kuhn-Tucker optimality conditions of the optimization problems faced by the market participants. Some theoretical results regarding the market prices in both markets are shown. We also illustrate the model on a representative, sample network of two production nodes, two consumption nodes with discretely distributed end-user demand and three seasons using four cases.
  • Thumbnail Image
    Item
    Analysis of Routing Strategies in Air Transportation Networks for Express Package Delivery Services
    (2005-07-06) Mahapatra, Subrat; Haghani, Ali; Civil Engineering; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)
    The package delivery industry plays a dominant role in our economy by providing consistent and reliable delivery of a wide range of goods. Shipment Service Providers (SSP) offer a wide range of service levels characterized by varying time windows and modes of operation and follow different network configurations and strategies for their operations. SSP operate vast systems of aircraft, trucks, sorting facilities, equipment and personnel to move packages between customer locations. Due to the high values of the assets involved in terms of aircraft and huge operational cost implications, any small percentage savings could result in the order of savings of millions of dollars for the company. The current research focuses on the Express Package Delivery Problem and the optimization of the air transportation network. SSP must determine which routes to fly, which fleets to assign to those routes and how to assign packages to those aircraft, all in response to demand projections and operational restrictions. The objective is to find the cost minimizing movement of packages from their origins to their destinations given the very tight service windows, and limited aircraft capacity. In the current research, we formulate the air transportation network as a mixed integer program which minimizes the total operating costs subject to the demand, capacity, time, aircraft and airport constraints. We use this model to study of various operational strategies and their potential cost implications. We consider two main operational strategies: one involving no intermediate stops on pick-up and delivery sides and the other involving one intermediate stop between origin and hub on pick-up side and between hub and destination on delivery side. Under each strategy, we analyze the cost implications under a single hub network configuration and regional hub network configuration. We study the impact of various routing scenarios, various variants and logical combinations of these scenarios which gives a clear understanding of the network structure. We perform an extensive sensitivity analysis to understand the implications of variation in demand, fixed cost of operation, variable cost of operation and bounds on the number of aircraft taking off and landing in the airports.
  • Thumbnail Image
    Item
    The Quick Time Dependent Quickest Flow Problem: A Lesson in Zero-Sum Cycles
    (2005-01-03) Dhundia, Harsh; Miller-Hooks, Elise D; Civil Engineering; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)
    A quick solution technique for the integral time-dependent quickest flow problem with no waiting is presented. The proposed technique is based on the successive shortest path approach and modifies an existing algorithm to improve its average performance. At each iteration, a reoptimization procedure is employed to determine the augmenting path given updates to the residual graph. The residual graph, by construction, almost always contains zero-sum cycles when employed in this context. These zero-sum cycles pose a unique problem for the reoptimization technique. A heuristic that can be embedded in the reoptimization algorithm to provide path solutions in the presence of zero-sum cycles has been proposed. In the computational experiments, the heuristic provided an optimal solution nearly 100% of the times. Further, a modified implementation of an existing path-finding algorithm has been used to solve the time-dependent quickest flow problem with source waiting.
  • Thumbnail Image
    Item
    THERMAL GENERATION ASSET VALUATION PROBLEMS IN A COMPETITIVE MARKET
    (2004-08-02) Zhu, Wei; Tseng, Chung-li; Civil Engineering; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)
    With deregulation in the electric power industry, traditional approaches for minimizing production costs have become unfit for the present competitive environment. Owners of generation assets must now consider price uncertainty in solving unit commitment problems for scheduling and operating their power plants. Operation flexibility of the generating assets, such as fuel switching and overfire, becomes an important issue. Because in a competitive market with volatile electricity prices, these flexibility may add significant values. On the other hand, operational constraints, such as ramp and minimum uptime/downtime constraints, present physical limits for the generating assets to flexibly react to rapid price changes, which have a negative effect on the asset value. Both of the operational flexibility and operational constraints must be considered simultaneously so as to achieve optimal operation under uncertainty. This dissertation devotes to this very important subject. Deregulation in the power industry allows new firms to freely enter the generation markets. As a result, capacity expansion is no longer the responsibility of local utility companies and has become a pure investment problem. Overestimating the value of a power may result in stranded capital for a long time period. Therefore, to ensure a successful investment a fair valuation method is essential. The generation asset valuation must fully account for market uncertainty, which results in not only risks but also opportunities. To minimize the risks, one must first have sound models for market uncertainties. In this research, we consider not only the uncertainties of electricity price and fuel price, but also environment temperature because some characteristics of power plants may be sensitive to the temperature. To fully capitalize on profitable opportunities arising in the marketplace due to price spreads of different commodities, such as fuel and electricity, a real options approach is considered, in which different options are exercised at different but `optimal' timings. Overall, this research is expected to contribute a new methodology for fair generation valuation that accounts for multiple and interdependent uncertainties and complex physical constraints. The proposed approach can help operators achieving optimal operation and investors making appropriate investment decisions. In the long run, customers also benefit from the improved societal efficiency.