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.

This thesis deals with shortest paths problem in graphs. Shortest paths problem is the basic issue of graph theory with many pracitcal applications. We can divide this problem into two following generalizations: single-source shortest path problem and all-pairs shortest paths problem. This text introduces principles and algorithms for generalizations. We describe both classical and new more efficient methods. It contains information about how some of these algorithms were implemented and offers an experimental comparison of these algorithms.

Cette thèse apporte plusieurs contributions dans le domaine des langages formels. Notre premier travail a été de montrer la pertinence des grammaires de graphes comme outil de démonstration de résultats fondamentaux sur les langages algébriques. Nous avons ainsi reformulé avec un point de vue géométrique les démonstrations du lemme des paires itérantes et du lemme de Parikh. Nous avons ensuite étendu aux graphes réguliers des algorithmes de base sur les graphes finis, notamment pour calculer des problèmes de plus court chemin. Ces extensions ont été faites par calcul de plus petits points fixes sur les grammaires de graphes. Enfin, nous avons caractérisé des familles générales de systèmes de récriture de mots dont la dérivation préserve la régularité ou l’algébricité. Ces familles ont été obtenues par décomposition de la dérivation en une substitution régulière suivie de la dérivation du système de Dyck / Pas de résumé en anglais

Intelligent Transportation System (ITS) provides a great platform for the planners to reduce environmental externalities from auto. We now have access to real time data. We have been using shortest path to provide route choice to the user. But we have the potential to add more variables in choosing routes. Real time data can be used to measure carbon di-oxide emission during a trip. Also, fuel efficiency can be measured using the real time data. Planners should use this potential of ITS to reduce the environmental impact. This paper thus try to evaluate if considering three variables shortest path, environmental impact and fuel efficiency together instead of only shortest path will change the route choice or not. It provides case studies on different types of routes and between different sets of origin /destination to evaluate the combined influence of these three variables on route choice.

Le besoin de se déplacer est un besoin fondamental dans la vie de tous les jours. Avec l’extension continue des zones urbaines, l’augmentation de la population et l’amélioration du niveau de vie des citoyens, le nombre de voitures ne cesse d’augmenter. Ceci étant, la plupart des transports publics proposés aujourd’hui obéissent à des règles qui manquent de souplesse et qui incluent rarement le caractère dynamique, en temps et en espace, de la demande. Cela réduit ainsi l’attractivité de ces services et les rendant même parfois difficilement supportables. De ce fait, la majorité des usagers utilisent encore leur propre véhicule. Ce grand nombre de véhicules, qui est en augmentation continue sur les réseaux routiers, provoque de nombreux phénomènes de congestion induisant une surconsommation de carburant, des émissions inutiles de gaz à effet de serre et une perte de temps importante. Pour y remédier, nous proposons dans cette thèse de nouveaux systèmes de déplacement des usagers avec différents modèles d’optimisation pour la mobilité partagée (covoiturage et taxis-partagés) ainsi que la combinaison de la mobilité partagée avec les transports publics. Les expérimentations sont réalisées sur de vrais réseaux routiers ainsi que sur des données réelles. Ces nouveaux systèmes améliorent considérablement la qualité de service des systèmes classiques existants en termes de coût et de flexibilité tout en ayant un temps de calcul raisonnable. / The travelling is a fundamental part of everyday life. The continuous expansion of urban areas combined with the population increasing and the improvement of life standards increases the need of mobility and the use of private cars. Furthermore, the majority of public transportations are subject to rules lacking of flexibility and rarely taking into account the dynamic context. The attractiveness of public transportation is therefore reduced and, as a consequence, its financial support, resulting in a further deterioration of the public services quality and flexibility. Therefore, the majority of users still use their own vehicles. The number of vehicles is continuously increasing on road networks causing important phenomena of congestion, high fuel consumption and emissions of greenhouse gases, time loss. This unpleasant situation forces communities to consider alternative solutions for the mobility such as ride-sharing, an interesting alternative to solo car use. The overall objective of this thesis is to propose new travel systems for users through the introduction of optimization models for shared mobility (ride-sharing and taxi-sharing) and the combination of shared mobility and public transportation. The computational experiments are carried out on real road networks and real data. Our numerical results show the effectiveness of our approach, which improves the quality of service compared to the traditional systems in terms of cost and flexibility. The running time remains reasonable to allow using our framework in real-time transportation applications.

Software engineering projects that utilize inappropriate pathfinding algorithms carry a significant risk of poor runtime performance for customers. Using social network theory, this experimental study examined the impact of algorithms, frameworks, and map complexity on elapsed time and computer memory consumption. The 1,800 2D map samples utilized were computer random generated and data were collected and processed using Python language scripts. Memory consumption and elapsed time results for each of the 12 experimental treatment groups were compared using factorial MANOVA to determine the impact of the 3 independent variables on elapsed time and computer memory consumption. The MANOVA indicated a significant factor interaction between algorithms, frameworks, and map complexity upon elapsed time and memory consumption, F(4, 3576) = 94.09, p < .001, h2 = .095. The main effects of algorithms, F(4, 3576) = 885.68, p < .001, h2 = .498; and frameworks, F(2, 1787) = 720,360.01, p .001, h2 = .999; and map complexity, F(2, 1787) = 112,736.40, p < .001, h2 = .992, were also all significant. This study may contribute to positive social change by providing software engineers writing software for complex networks, such as analyzing terrorist social networks, with empirical pathfinding algorithm results. This is crucial to enabling selection of appropriately fast, memory-efficient algorithms that help analysts identify and apprehend criminal and terrorist suspects in complex networks before the next attack.