No description available.

No description available.

No description available.

No description available.

This thesis examines the existence of a dominant route between a hub pair and factors that influence bike share cyclists route choices. This research collects 132,396 hub to-hub global positioning system (GPS) trajectories over a 12-month period between April 1, 2015 and March 31, 2016 from 750 bicycles provided by a bike share program (BSP) called SoBi (Social Bicycles) Hamilton. Then, a GIS-based map-matching toolkit is used to convert GPS points to map-matched trips and generate a series of route attributes. In order to create choice sets, unique routes between the same hub pair are extracted from all corresponding repeated trips using a link signature tool. The results from t statistics and Path-size logit models indicate that bike share cyclists are willing to detour for some positive features, such as bicycle facilities and low traffic volumes, but they also try to avoid too circuitous routes, turns, and steep slopes over 4% though detouring may come with a slight increase in turns. This research not only helps us understand BSP cyclist route preferences but also presents a GIS-based approach to determine potential road segments for additional bike facilities on the basis of such preferences. / Thesis / Master of Science (MSc)

This dissertation contributes to the ongoing national project concerning the \emph{Next Generation Air Transportation System} (NextGen) that endeavors, in particular, to reshape the management of air traffic in the continental United States. Our work is part of this effort and mainly concerns modeling and algorithmic enhancements to the Airspace Planning and Collaborative Decision-Making Model (APCDM). First, we augment the APCDM to study an \emph{Airspace Flow Program} (AFP) in the context of weather-related disruptions. The proposed model selects among alternative flight plans for the affected flights while simultaneously (a) integrating slot-exchange mechanisms induced by multiple Ground Delay Programs (GDPs) to permit airlines to improve flight efficiencies through a mediated bartering of assigned slots, and (b) considering issues related to sector workloads, airspace conflicts, as well as overall equity concerns among the involved airlines in regard to accepted slot trades and flight plans. More specifically, the APCDM is enhanced to include the following: a. The revised model accommodates continuing flights, where some flight cannot depart until a prerequisite flight has arrived. Such a situation arises, for example, when the same aircraft will be used for the departing flight. b. We model a slot-exchange mechanism to accommodate flights being involved in multiple trade offers, and to permit slot trades at multiple GDP airports (whence the flight connection constraints become especially relevant). We also model flight cancelations whereby, if a flight assigned to a particular slot is canceled, the corresponding vacated slot would be made available for use in the slot-exchange process. c. Alternative equity concepts are presented, which more accurately reflect the measures used by the airlines. d. A reduced variant of the APCDM, referred to as \textbf{APCDM-Light}, is also developed. This model serves as a fast-running version of APCDM to be used for quick-turn analyses, where the level of modeling detail, as well as data requirements, are reduced to focus only on certain key elements of the problem. e. As an alternative for handling large-scale instances of APCDM more effectively, we present a \emph{sequential variable fixing heuristic} (SFH). The list of flights is first partitioned into suitable subsets. For the first subset, the corresponding decision variables are constrained to be binary-valued (which is the default for these decision variables), while the other variables are allowed to vary continuously between 0 and 1. If the resulting solution to this relaxed model is integral, the algorithm terminates. Otherwise, the binary variables are fixed to their currently prescribed values and another subset of variables is designated to be binary constrained. The process repeats until an integer solution is found or the heuristic encounters infeasibility. f. We experiment with using the APCDM model in a \emph{dynamic, rolling-horizon framework}, where we apply the model on some periodic basis (e.g., hourly), and where each sequential run of the model has certain flight plan selections that are fixed (such as flights that are already airborne), while we consider the selection among alternative flight plans for other imminent flights in a look-ahead horizon (e.g., two hours). These enhancements allow us to significantly expand the functionality of the original APCDM model. We test the revised model and its variants using realistic data derived from the \emph{Enhanced Traffic Management System} (ETMS) provided by the \emph{Federal Aviation Administration} (FAA). One of the new equity methods, which is based on average delay per passenger (or weighted average delay per flight), turns out to be a particularly robust way to model equity considerations in conjunction with sector workloads, conflict resolution, and slot-exchanges. With this equity method, we were able to solve large problem instances (1,000 flights) within 30 seconds on average using a 1\% optimality tolerance. The model also produced comparable solutions within about 20 seconds on average using the Sequential Fixing Heuristic (SFH). The actual solutions obtained for these largest problem instances were well within 1\% of the best known solution. Furthermore, our computations revealed that APCDM-Light can be readily optimized to a 0.01\% tolerance within about 5 seconds on average for the 1,000 flight problems. Thus, the augmented APCDM model offers a viable tool that can be used for tactical air traffic management purposes as an airspace flow program (particularly, APCDM-Light), as well as for strategic applications to study the impact of different types of trade restrictions, collaboration policies, equity concepts, and airspace sectorizations. The modeling of slot ownership in the APCDM motivates another problem: that of generating detoured flight plans that must arrive at a particular slot time under severe convective weather conditions. This leads to a particular class of network flow problems that seeks a shortest path, if it exists, between a source node and a destination node in a connected digraph $G(N,A)$, such that we arrive at the destination at a specified time while leaving the source no earlier than a lower bounding time, and where the availability of each network link is time-dependent in the sense that it can be traversed only during specified intervals of time. We refer to this problem as the \emph{reverse time-restricted shortest path problem} (RTSP). We show that RTSP is NP-hard in general and propose a dynamic programming algorithm for finding an optimal solution in pseudo-polynomial time. Moreover, under a special regularity condition, we prove that the problem is polynomially solvable with a complexity of order $O(|N / A|)$. Computational results using real flight generation test cases as well as random simulated problems are presented to demonstrate the efficiency of the proposed solution procedures. The current airspace configuration consists of sectors that have evolved over time based on historical traffic flow patterns. \citet{kopardekar_dyn_resect_2007} note that, given the current airspace configuration, some air traffic controller resources are likely under-utilized, and they also point out that the current configuration limits flexibility. Moreover, under the free-flight concept, which advocates a relaxation of waypoint traversals in favor of wind-optimized trajectories, the current airspace configuration will not likely be compatible with future air traffic flow patterns. Accordingly, one of the goals for the \emph{NextGen Air Transportation System} includes redesigning the airspace to increase its capacity and flexibility. With this motivation, we present several methods for defining sectors within the \emph{National Airspace System} (NAS) based on a measure of sector workload. Specifically, given a convex polygon in two-dimensions and a set of weighted grid points within the region encompassed by the polygon, we present several mixed-integer-programming-based algorithms to generate a plane (or line) bisecting the region such that the total weight distribution on either side of the plane is relatively balanced. This process generates two new polygons, which are in turn bisected until some target number of regions is reached. The motivation for these algorithms is to dynamically reconfigure airspace sectors to balance predicted air-traffic controller workload. We frame the problem in the context of airspace design, and then present and compare four algorithmic variants for solving these problems. We also discuss how to accommodate monitoring, conflict resolution, and inter-sector coordination workloads to appropriately define grid point weights and to conduct the partitioning process in this context. The proposed methodology is illustrated using a basic example to assess the overall effect of each algorithm and to provide insights into their relative computational efficiency and the quality of solutions produced. A particular competitive algorithmic variant is then used to configure a region of airspace over the U.S. using realistic flight data. The development of the APCDM is part of an ongoing \emph{NextGen} research project, which envisages the sequential use of a variety of models pertaining to three tiers. The \emph{Tier 1} models are conceived to be more strategic in scope and attempt to identify potential problematic areas, e.g., areas of congestion resulting from a severe convective weather system over a given time-frame, and provide aggregate measures of sector workloads and delays. The affected flow constrained areas (FCAs) highlighted by the results from these \emph{Tier 1} models would then be analyzed by more detailed \emph{Tier 2} models, such as APCDM, which consider more specific alternative flight plan trajectories through the different sectors along with related sector workload, aircraft conflict, and airline equity issues. Finally, \emph{Tier 3} models are being developed to dynamically examine smaller-scaled, localized fast-response readjustments in air traffic flows within the time-frame of about an hour prior to departure (e.g., to take advantage of a break in the convective weather system). The APCDM is flexible, and perhaps unique, in that it can be used effectively in all three tiers. Moreover, as a strategic tool, analysts could use the APCDM to evaluate the suitability of potential airspace sectorization strategies, for example, as well as identify potential capacity shortfalls under any given sector configuration. / Ph. D.

In theoretical computer science, various notions of efficiency are used for algorithms. The most commonly used notion is worst-case efficiency, which is defined by requiring polynomial worst-case running time. Another commonly used notion is average-case efficiency for random inputs, which is roughly defined as having polynomial expected running time with respect to the random inputs. Depending on the actual notion of efficiency one uses, the approximability of a combinatorial optimization problem can be very different. In this dissertation, the approximability of three classical combinatorial optimization problems, namely Independent Set, Coloring, and Shortest Common Superstring, is investigated for different notions of efficiency. For the three problems, approximation algorithms are given, which guarantee approximation ratios that are unachievable by worst-case efficient algorithms under reasonable complexity-theoretic assumptions. The algorithms achieve polynomial expected running time for different models of random inputs. On the one hand, classical average-case analyses are performed, using totally random input models as the source of random inputs. On the other hand, probabilistic analyses are performed, using semi-random input models inspired by the so called smoothed analysis of algorithms. Finally, the expected performance of well known greedy algorithms for random inputs from the considered models is investigated. Also, the expected behavior of some properties of the random inputs themselves is considered.

Denna rapport behandlar en undersökning av olika lastbalanseringsalgoritmer i Linux Virtual Server. Undersökningen har gjorts i ett webbkluster (Apache var webbservern som användes) med tre heterogena noder, där operativsystemet var den detalj som skiljde dem åt. Operativsystemen som ingick i undersökningen var Windows Server 2008 R2, CentOS 6.2 och FreeBSD 9.0. De faktorer som undersöktes mellan de olika algoritmerna var klustrets genomsnittliga svarstid vid olika belastning och hur många anslutningar som kunde hanteras av klustret, detta gjordes med verktyget httperf. Undersökningen ger svar på hur ett heterogent webbklusters genomsnittligasvarstid och arbetskapacitet kan skilja sig åt beroende på vilken algoritm som används för lastbalansering. Resultatet visar att den genomsnittliga svarstiden håller sig låg tills en hastig stigning inträffar. Shortest Expected Delay och Weighted Least-Connection Scheduling kunde hantera störst antal anslutningar. / This report covers an investigation of different load balancing algorithms in Linux Virtual Server. The investigation was done in a web cluster (with Apache as the software being used) consisting of three heterogeneous nodes, where the operating system was the detail that differentiated the nodes. The operating systems that were used in the investigation were Windows Server 2008 R2, CentOS 6.2 and FreeBSD 9.0. The factors examined were average response time at different load and how many connections the cluster could cope with, these factors were examined by measurements taken with the tool httperf. The investigation gives an answer to how a heterogeneous web clustersaverage response time and working capacity can be affected by the choice of load balancing algorithm. The result shows that the average response time stays low until a sudden rise occurs. Shortest Expected Delay and Weighted Least-Connection Scheduling could handle the largest number of connections.

In theoretical computer science, various notions of efficiency are used for algorithms. The most commonly used notion is worst-case efficiency, which is defined by requiring polynomial worst-case running time. Another commonly used notion is average-case efficiency for random inputs, which is roughly defined as having polynomial expected running time with respect to the random inputs. Depending on the actual notion of efficiency one uses, the approximability of a combinatorial optimization problem can be very different. In this dissertation, the approximability of three classical combinatorial optimization problems, namely Independent Set, Coloring, and Shortest Common Superstring, is investigated for different notions of efficiency. For the three problems, approximation algorithms are given, which guarantee approximation ratios that are unachievable by worst-case efficient algorithms under reasonable complexity-theoretic assumptions. The algorithms achieve polynomial expected running time for different models of random inputs. On the one hand, classical average-case analyses are performed, using totally random input models as the source of random inputs. On the other hand, probabilistic analyses are performed, using semi-random input models inspired by the so called smoothed analysis of algorithms. Finally, the expected performance of well known greedy algorithms for random inputs from the considered models is investigated. Also, the expected behavior of some properties of the random inputs themselves is considered.

With the economic growth, the number of motor vehicles has increased rapidly for the last decades, especially in developing countries like China and India. Availability of more vehicles makes it more convenient for people to travel and merchandise transport. The increase of the number of vehicles also brings stresses to public traffic and pollution to the environment. When the number of vehicles on the road is over the available space, it results in traffic congestion. The problem is being studied and there are several solutions to it, like building more roads, rebuilding the existing streets and enlarging the cities. Based on the traffic reason and the environment reason, the government and the institute of environmental protection appeal to the public to take public transport means instead of private cars. But the measure affects the utilization ofmotor vehicles. Global Positioning System (GPS) provides autonomous geo-spatial positioningand navigation service. Once the user enters the destination, the navigation service will show the shortest path from the location of the user to the destination. Following the guide makes the vehicles running purposively, and it is also favorable for traffic control and management. Theoretically, if the diver keeps the same driving mode, the shortest path will cost the shortest time, but in reality, the traffic environment is complex and the driving speed is variable thus the shortest path is probably not the fastest path. In this study, the hinder factors of the speed and traffic are fixed constructions on the road, like: turnings, hospitals, schools, residential areas, traffic lights and the user-controlled factor (sites of traffic jams, accidents, and temporary construction on the road). We take the hinderfactors of traffic and driving speed into consideration while providing the route plan, finding the shortest-time path, and showing the result as an online map via the web Geographic Information System (GIS) application. We show that reducing the travelling time of motor vehicles, makes the traffic flow more rapid and efficient. Alsoreducing the emission time of motor vehicles, diminishes the greenhouse effect. Beside these, the achievement of our study also shows that the public can take advantage of open source tools and data to build their GIS application to do spatial and data analysis.