No description available.

No description available.

In this dissertation we introduce a new class of pursuit-evasion games; the herding problem. Unlike regular pursuit evasion games where the pursuer aims to hunt the evader the objective of the pursuer in this game is to drive the evader to a certain location on the x-y grid. The dissertation deals with this problem using two different methodologies. In the first, the problem is introduced in the continuous-time, continuous-space domain. The continuous time model of the problem is proposed, analyzed and we came up with an optimal control law for the pursuer is obtained so that the evader is driven to the desired destination position in the x-y grid following the local shortest path in the Euler Lagrange sense. Then, a non-holonomic realization of the two agents is proposed. In this and we show that the optimal control policy is in the form of a feedback control law that enables the pursuer to achieve the same objective using the shortest path. The second methodology deals with the discrete model representation of the problem. In this formulation, the system is represented by a finite di-graph. In this di-graph, each state of the system is represented by a node in the graph. Applying dynamic programming technique and shortest path algorithms over the finite graph representing the system, we come up with the optimal control policy that the pursuer should follow to achieve the desired goal. To study the robustness, we formulate the problem in a stochastic setting also. We analyze the stochastic model and derive an optimal control law in this setting. Finally, the case with active evader is considered, the optimal control law for this case is obtained through the application of dynamic programming technique. / Ph. D.

TRANSIMS (Transportation Analysis Simulation System) is part of a multi-track Travel Model Improvement Program sponsored by the U. S. Department of Transportation (DOT), and the Environmental Protection Agency (EPA). The main objective of this thesis is to enhance and implement a principal module in TRANSIMS, called the Route Planner Module. The purpose of the Route Planner Module is to find time-dependent label-constrained shortest paths for transportation activities performed by travelers in the system. There are several variations of shortest path problems and algorithms that vary by application, contexts, complexity, required data, and computer implementation techniques. In general, these variants require some combination of the following inputs: a network consisting of nodes and links, and a travel time function on each link, which could be a time-independent or a time-dependent function, where the time-dependent functions account for time-of-day delays resulting from actual travel conditions such as peak-hour congestion. The problem then seeks a shortest path between one or more origin-destination pairs. A new variant, introduced in the context of TRANSIMS and which is the focus of the present study, also specifies labels for each arc denoting particular modes of travel, along with strings of admissible labels that delineate the permissible travel mode sequences that could be adopted by the user in traveling from the origin to the destination of the trip. The technique adopted by TRANSIMS to identify a suitable travel route for any user is a variant of Dijkstra's procedure for finding shortest paths, which is suitably modified to accommodate time-dependent travel times and label sequence constraints. The underlying problem is referred to as a Time-Dependent Label-Constrained Shortest Path Problem. The main objective of this research is to improve upon this procedure and study its implementation in order to develop a more effective scheme for determining time-dependent label-constrained shortest paths as a practical routing tool in multimodal transportation networks. Specifically, we enhance the following features of this procedure: (a) We recommend a method to work implicitly with a certain composition graph G* that combines the transportation network with the admissible label-sequence graph. This graph G* captures all possible paths for a given single trip starting from the origin node and ending at the destination node, while conforming with the admissible mode string. (b) We use more modern partitioned shortest path algorithmic schemes to implement the time-dependent label-constrained procedure. (c) We introduce the notion of curtailing search based on various indicators of progress and projected travel times to complete the trip. Finally, computer programs in C++ are written to implement the proposed overall algorithm, and are applied to solve some real multimodal transportation network problems. The indicators used to evaluate the performance of the algorithm include (i) time taken for computation on the real network, (ii) quality of solution obtained, (iii) ease of implementation, and (iv) extensibility of the algorithm for solving other variants of the shortest path problem. The results exhibit that the proposed algorithm, even without the approximate curtailing of the search process, exhibits good performance in finding optimal routes for real multimodal transportation networks. Although the various heuristic curtailments result in only approximate solutions, typically, they run much faster than the exact algorithm for the intuitive reason that the shortest path tree developed grows more pointedly in the direction of the destination. Among the different strategies implemented, our results suggest that the scheme based on the geometric structure of the underlying network, using either a constant predictive term, or multiplying this term with a suitable exponential decay function, yields an attractive candidate for heuristically curtailing the search. / Master of Science

abstract: Vehicles powered by electricity and alternative-fuels are becoming a more popular form of transportation since they have less of an environmental impact than standard gasoline vehicles. Unfortunately, their success is currently inhibited by the sparseness of locations where the vehicles can refuel as well as the fact that many of the vehicles have a range that is less than those powered by gasoline. These factors together create a "range anxiety" in drivers, which causes the drivers to worry about the utility of alternative-fuel and electric vehicles and makes them less likely to purchase these vehicles. For the new vehicle technologies to thrive it is critical that range anxiety is minimized and performance is increased as much as possible through proper routing and scheduling. In the case of long distance trips taken by individual vehicles, the routes must be chosen such that the vehicles take the shortest routes while not running out of fuel on the trip. When many vehicles are to be routed during the day, if the refueling stations have limited capacity then care must be taken to avoid having too many vehicles arrive at the stations at any time. If the vehicles that will need to be routed in the future are unknown then this problem is stochastic. For fleets of vehicles serving scheduled operations, switching to alternative-fuels requires ensuring the schedules do not cause the vehicles to run out of fuel. This is especially problematic since the locations where the vehicles may refuel are limited due to the technology being new. This dissertation covers three related optimization problems: routing a single electric or alternative-fuel vehicle on a long distance trip, routing many electric vehicles in a network where the stations have limited capacity and the arrivals into the system are stochastic, and scheduling fleets of electric or alternative-fuel vehicles with limited locations to refuel. Different algorithms are proposed to solve each of the three problems, of which some are exact and some are heuristic. The algorithms are tested on both random data and data relating to the State of Arizona. / Dissertation/Thesis / Ph.D. Industrial Engineering 2014

Many modern mobile communication devices are equipped with a GPS receiver and anavigation tool. These devices are useful when a user seeks to reach a specified destinationas soon as possible, but may not be so when he/she only needs to arrive at thedestination in time and wants to focus on some activities on the way. To deal with thislatter situation, a method and device called “Space Time Alarm Clock” is presented forhelping the user reach the destination by a specified deadline and inform the user aboutthe consequences of his/her decisions. It does so by continuously and efficiently computinghow much more time the user may stay at his/her current location without failing toreach the destination by the deadline. Furthermore, it determines the possible movementchoices that a user can make with regards to an underlying road network, it computesthe shortest travel time associated with each choice and informs the user about the consequencesof his/her decisions. Advantage of this approach is that it works completelyin the background so that the user‘s en-route activities will never be interfered with. The“Space Time Alarm Clock” was implemented for Stockholm, where it was tested.

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.

Modern vehicles have an increasing number of advanced features requiring network coverage in order to function properly. In order to facilitate the requirements of such features and allow more advanced applications, we consider the possibility of planning routes that take signal strength into consideration. Previous work have shown the relationship between TCP throughput/goodput and signal strength. In this thesis signal-aware route planning is presented, implemented, and validated. Crowd-sourced map and signal data (3G) from two sources is used for building a signal coverage map. The signal and map data is validated in a field experiment, where routes were travelled while measuring the signal strength. The field experiment showed gains in signal characteristics when deviating from the shortest possible path. The average signal strength increased by 11 dBm between algorithms and the shortest possible path. Lastly, routes were planned for all possible sources and destinations in a given urban area. The results of this calculation confirms the patterns found in the field experiment.

We provide a formal mathematical definition of the Shortest Paths for All Flows (SP-AF) problem and provide many efficient algorithms. The SP-AF problem combines the well known Shortest Paths (SP) and Bottleneck Paths (BP) problems, and can be solved by utilising matrix multiplication. Thus in our research of the SP-AF problem, we also make a series of contributions to the underlying topics of the SP problem, the BP problem, and matrix multiplication. For the topic of matrix multiplication we show that on an n-by-n two dimensional (2D) square mesh array, two n-by-n matrices can be multiplied in exactly 1.5n ‒ 1 communication steps. This halves the number of communication steps required by the well known Cannon’s algorithm that runs on the same sized mesh array. We provide two contributions for the SP problem. Firstly, we enhance the breakthrough algorithm by Alon, Galil and Margalit (AGM), which was the first algorithm to achieve a deeply sub-cubic time bound for solving the All Pairs Shortest Paths (APSP) problem on dense directed graphs. Our enhancement allows the algorithm by AGM to remain sub-cubic for larger upper bounds on integer edge costs. Secondly, we show that for graphs with n vertices, the APSP problem can be solved in exactly 3n ‒ 2 communication steps on an n-by-n 2D square mesh array. This improves on the previous result of 3.5n communication steps achieved by Takaoka and Umehara. For the BP problem, we show that we can compute the bottleneck of the entire graph without solving the All Pairs Bottleneck Paths (APBP) problem, resulting in a much more efficient time bound. Finally we define an algebraic structure called the distance/flow semi-ring to formally introduce the SP-AF problem, and we provide many algorithms for solving the Single Source SP-AF (SSSP-AF) problem and the All Pairs SP-AF (APSP-AF) problem. For the APSP-AF problem, algebraic algorithms are given that utilise faster matrix multiplication over a ring.

O Problema dos K Menores Caminhos é uma generalização do Problema do Menor Caminho, em que desejamos encontrar os K caminhos de menor custo entre dois vértices de um grafo. Estudamos e implementamos algoritmos que resolvem esse problema em grafos dirigidos, com peso nos arcos e que permitem apenas caminhos sem repetição de vértices na resposta. Comparamos seus desempenhos utilizando grafos do 9th DIMACS Implementation Challenge. Identificamos os pontos fortes e fracos de cada algoritmo, e propusemos uma variante híbrida dos algoritmos de Feng e de Pascoal. Essa variante proposta obteve desempenho superior aos algoritmos base em alguns grafos, e resultado superior a pelo menos um deles na grande maioria dos testes. / The K-Shortest Path Problem is a generalization of the Shortest Path Problem, in which we must find the K paths between two vertices in a graph that have the lowest costs. We study some K-Shortest Path Problem algorithms applied to weighted directed graphs, allowing only paths with no repeated vertices. We compare empirically implementation of some algorithms, using instance graphs from the 9th DIMACS Implementation Challenge. We identify the strengths and weaknesses of each algorithm, and we propose a hybrid version of Feng\'s and Pascoal\'s algorithms. This proposed variant achieve better perfomance compared to both base algorithms in some graphs, and it is better than at least one of them in most cases.