This thesis proposes a novel and efficient method (Method of Evolving Junctions) for solving optimal control problems with path constraints, and whose optimal paths are separable. A path is separable if it is the concatenation of finite number of subarcs that are optimal and either entirely constraint active or entirely constraint inactive. In the case when the subarcs can be computed efficiently, the search for the optimal path boils down to determining the junctions that connect those subarcs. In this way, the original infinite dimensional problem of finding the entire path is converted into a finite dimensional problem of determine the optimal junctions. The finite dimensional optimization problem is then solved by a recently developed global optimization strategy, intermittent diffusion. The idea is to add perturbations (noise) to the gradient flow intermittently, which essentially converts the ODE's (gradient descent) into a SDE's problem. It can be shown that the probability of finding the globally optimal path can be arbitrarily close to one. Comparing to existing methods, the method of evolving junctions is fundamentally faster and able to find the globally optimal path as well as a series of locally optimal paths. The efficiency of the algorithm will be demonstrated by solving path planning problems, more specifically, finding the optimal path in cluttered environments with static or dynamic obstacles.

In this thesis, we introduce three new approaches for solving the single source shortest path (SSSP) problem in nearly acyclic directed graphs, and algorithms based on these approaches. In the first approach, we extend a technique of strongly connected components (sc-components) decomposition by Takaoka [23], and the generalized decomposition approach is called a higher-order decomposition. According to Takaoka's definition of acyclicity, the degree of cyclicity of a graph G, cyc(G), is defined by the maximum cardinality of the strongly connected components of G. Based on the higher-order decomposition, we give a generalization of Takaoka's definition of acyclicity. That is, the degree of cyclicity cych(G) is the maximum cardinality of the hth order strongly connected components of G, where h is the number of times that the graph has been decomposed. Then, the original definition introduced by Takaoka [23] can be presented as: The degree of cyclicity cyc(G) is the maximum cardinality of the 1th order strongly connected components of G. The second approach presents a new method for measuring acyclicity based on modifications to two existing methods. In the new method, we decompose the given graph into a 1-dominator set, which is a set of acyclic subgraphs, where each sub-graph is dominated by one trigger vertex. Meanwhile we compute sc-components of a degenerated graph derived from triggers. Using this preprocessing, we can efficiently compute the single source shortest paths (SSSPs) for nearly acyclic graphs in O(m + r logl ) time, where r is the size of the 1-dominator set, and l is the size of the largest sc-component. In the third approach, we modify the concept of a 1-dominator set to that of a 1-2-dominator set, and achieve O(m + r²) time to compute a 1- 2-dominator set in a graph. Each of acyclic sub-graphs obtained by the 1-2-dominator set are dominated by one or two trigger vertices cooperatively. Such sub-graphs are potentially larger than those decomposed by the 1-dominator set. Thus fewer trigger vertices are needed to cover the graph, that is, rʹ ≤ r, where rʹ is the number of triggers in the 1-2-dominator set. When rʹ is much smaller than r, we can efficiently compute SSSPs in O(m + rʹlogrʹ) time.

In recent years the growth in demand for multimedia applications delivered over a network has been extensive illustrated by the phenomenal expansion of the World Wide Web in today's Internet. Increasing amounts of electronic information are presented in a multimedia format and delivered over networks, which generates increased traffic demands. In short, future networks will not only comprise multiple, interconnected data transport platforms but will also need to handle an increasing range of distributed multimedia services, delivered to a diverse user community that is increasingly becoming mobile.

Shortest path problems arise in a variety of applications ranging from transportation planning to network routing among others. One group of these problems involves finding shortest paths in graphs where the edge weights are defined by probability distributions. While some research has addressed the problem of finding a single shortest path, no research has been done on finding multiple paths in such graphs. This thesis addresses the problem of finding paths for multiple robots through a graph in which the edge weights represent the probability that each edge will fail. The objective is to find paths for n robots that maximize the probability that at least k of them will arrive at the destination. If we make certain restrictions on the edge weights and topology of the graph, this problem can be solved in O(n log n)time. If we restrict only the topology, we can find approximate solutions which are still guaranteed to be better than the single most reliable path.

In this thesis, we present two e cent algorithms to compute shortest path between pair of vertices in directed and undirected double-loop networks. The algorithm for undirected double-loop networks is based on the concept "packed basis" proposed by Janez Zerrovnik and Toma z Pisanski. With O(logN) preprocessing time, both algorithms need only constant time to compute the shortest path between any pair of vertices in the network. This is an improvement of the best known algorithm, which needs O(l) time, where l is the length of the path in the directed double-loop networks. These algo- rithms are useful in message routing in the double-loop networks. Once the network has been constructed, the parameters for computing the shortest paths can be computed. At the time a message is to be delivered, the algo- rithm needs only constant time to determine which edge the message should be sent.

In this dissertation, we consider two important problems pertaining to the analysis of transportation systems. The first of these is an approach-dependent, time-dependent, label-constrained shortest path problem that arises in the context of the Route Planner Module of the Transportation Analysis Simulation System (TRANSIMS), which has been developed by the Los Alamos National Laboratory for the Federal Highway Administration. This is a variant of the shortest path problem defined on a transportation network comprised of a set of nodes and a set of directed arcs such that each arc has an associated label designating a mode of transportation, and an associated travel time function that depends on the time of arrival at the tail node, as well as on the node via which this node was approached. The lattermost feature is a new concept injected into the time-dependent, label-constrained shortest path problem, and is used to model turn-penalties in transportation networks. The time spent at an intersection before entering the next link would depend on whether we travel straight through the intersection, or make a right turn at it, or make a left turn at it. Accordingly, we model this situation by incorporating within each link's travel time function a dependence on the link via which its tail node was approached. We propose two effective algorithms to solve this problem by adapting two efficient existing algorithms to handle time dependency and label constraints: the Partitioned Shortest Path (PSP) algorithm and the Heap-Dijkstra (HP-Dijkstra) algorithm, and present related theoretical complexity results. In addition, we also explore various heuristic methods to curtail the search. We explore an Augmented Ellipsoidal Region Technique (A-ERT) and a Distance-Based A-ERT, along with some variants to curtail the search for an optimal path between a given origin and destination to more promising subsets of the network. This helps speed up computation without sacrificing optimality. We also incorporate an approach-dependent delay estimation function, and in concert with a search tree level-based technique, we derive a total estimated travel time and use this as a key to prioritize node selections or to sort elements in the heap. As soon as we reach the destination node, while it is within some p% of the minimum key value of the heap, we then terminate the search. We name the versions of PSP and HP-Dijkstra that employ this method as Early Terminated PSP (ET-PSP) and Early Terminated Heap-Dijkstra (ETHP-Dijkstra) algorithms. All of these procedures are compared with the original Route Planner Module within TRANSIMS, which is implemented in the Linux operating system, using C++ along with the g++ GNU compiler. Extensive computational testing has been conducted using available data from the Portland, Oregon, and Blacksburg, Virginia, transportation networks to investigate the efficacy of the developed procedures. In particular, we have tested twenty-five different combinations of network curtailment and algorithmic strategies on three test networks: the Blacksburg-light, the Blacksburg-full, and the BigNet network. The results indicate that the Heap-Dijkstra algorithm implementations are much faster than the PSP algorithmic approaches for solving the underlying problem exactly. Furthermore, mong the curtailment schemes, the ETHP-Dijkstra with p=5%, yields the best overall results. This method produces solutions within 0.37-1.91% of optimality, while decreasing CPU effort by 56.68% at an average, as compared with applying the best available exact algorithm. The second part of this dissertation is concerned with the Classification and Regression Tree (CART) algorithm, and its application to the Activity Generation Module of TRANSIMS. The CART algorithm has been popularly used in various contexts by transportation engineers and planners to correlate a set of independent household demographic variables with certain dependent activity or travel time variables. However, the algorithm lacks an automated mechanism for deriving classification trees based on optimizing specified objective functions and handling desired side-constraints that govern the structure of the tree and the statistical and demographic nature of its leaf nodes. Using a novel set partitioning formulation, we propose new tree development, and more importantly, optimal pruning strategies to accommodate the consideration of such objective functions and side-constraints, and establish the theoretical validity of our approach. This general enhancement of the CART algorithm is then applied to the Activity Generator module of TRANSIMS. Related computational results are presented using real data pertaining to the Portland, Oregon, and Blacksburg, Virginia, transportation networks to demonstrate the flexibility and effectiveness of the proposed approach in classifying data, as well as to examine its numerical performance. The results indicate that a variety of objective functions and constraints can be readily accommodated to efficiently control the structural information that is captured by the developed classification tree as desired by the planner or analyst, dependent on the scope of the application at hand. / Ph. D.

This paper addresses sensitivity analysis questions concerning the shortest path problem and the maximum capacity path problem in an undirected network. For both problems, we determine the maximum and minimum weights that each edge can have so that a given path remains optimal. For both problems, we show how to determine these maximum and minimum values for all edges in O(m + K log K) time, where m is the number of edges in the network, and K is the number of edges on the given optimal path.

The problem of computing K shortest loopless paths, or ranking of the K shortest loopless paths between a pair of given vertices in a network is a well-studied generalization of shortest path problem. The K shortest paths problem determines not only one shortest path but the K best shortest paths from s to t in an increasing order of weight of the paths. Yen’s algorithm is known to be the efficient and widely used algorithm for determining K shortest loopless paths. Here, we introduce a new algorithm by modifying the Yen’s algorithm in the following way: instead of removing the vertices and the edges from the graph, we store them in two different sets. Then we modified the Dijkstra’s algorithm by taking these two sets into consideration. Thus the algorithm applies glass box methodology by using the modified Dijkstra’s algorithm for our dedicated purpose. Thus the efficiency is improved. The computational results conducted over different datasets, shows the proposed algorithm has better performance results.

Το πρόβλημα εύρεσης συντομότερης διαδρομής είναι ένα από τα πιο θεμελιώδη προβλήματα μονοκριτηριακής βελτιστοποίησης σε δίκτυα. Σε πολλές εφαρμογές ωστόσο, μας ενδιαφέρουν περισσότερα από ένα κριτήρια προς βελτιστοποίηση. Για παράδειγμα, στην δρομολόγηση σε ένα οδικό δίκτυο με διόδια, μας ενδιαφέρει ταυτόχρονα η ελαχιστοποίηση του χρόνου και του κόστους σε χρήματα. Παρόμοια παραδείγματα βρίσκουμε και στον χώρο των δικτύων τηλεπικοινωνιών, όπου εξετάζονται κριτήρια όπως η καθυστέρηση, η πιθανότητα λάθους, ο αριθμός συνδέσμων και άλλα. Σε αυτές οι περιπτώσεις η ``καλύτερη\\\\ / The shortest path problem is perhaps the most fundamental single objective optimization problem in networks. In many applications however we are interested in more than two objectives. For example, when routing in a network with tolls, we are interested in minimizing both the time and the cost. Similar examples can be also found in communication networks where the criteria under investigation are the delay, the fault probability, the number of hops and other. In such cases the \\\\

In this thesis, we study robust combinatorial problems with interval data. We introduce several new measures of robustness in response to the drawbacks of existing measures of robustness. The idea of these new measures is to ensure that the solutions are satisfactory for the decision maker in all scenarios, including the worst case scenario. Therefore, we have introduced a threshold over the worst case costs, in which above this threshold, solutions are no longer satisfactory for the decision maker. It is, however, important to consider other criteria than just the worst case. Therefore, in each of these new measures, a second criteria is used to evaluate the performance of the solution in other scenarios such as the best case one. We also study the robust deviation p-elements problem. In fact, we study when this solution is equal to the optimal solution in the scenario where the cost of each element is the midpoint of its corresponding interval. Then, we finally formulate the robust combinatorial problem with interval data as a bicriteria problem. We also integrate the decision maker's preferences over certain types of solutions into the model. We propose a method that uses these preferences to find the set of solutions that are never preferred by any other solution. We call this set the final set. We study the properties of the final sets from a coherence point of view and from a robust point of view. From a coherence point of view, we study necessary and sufficient conditions for the final set to be monotonic, for the corresponding preferences to be without cycles, and for the set to be stable. Those that do not satisfy these properties are eliminated since we believe these properties to be essential. We also study other properties such as the transitivity of the preference and indifference relations and more. We note that many of our final sets are included in one another and some are even intersections of other final sets. From a robust point of view, we compare our final sets with different measures of robustness and with the first- and second-degree stochastic dominance. We show which sets contain all of these solutions and which only contain these types of solutions. Therefore, when the decision maker chooses his preferences to find the final set, he knows what types of solutions may or may not be in the set. Lastly, we implement this method and apply it to the Robust Shortest Path Problem. We look at how this method performs using different types of randomly generated instances.