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.

Signaling pathways are widely studied in systems biology. Several databases catalog our knowledge of these pathways, including the proteins and interactions that comprise them. However, high-quality curation of this information is slow and painstaking. As a result, many interactions still lack annotation concerning the pathways they participate in. A natural question that arises is whether or not it is possible to automatically leverage existing annotations to identify new interactions for inclusion in a given pathway. Here, we present RegLinker, an algorithm that achieves this purpose by computing multiple short paths from pathway receptors to transcription factors (TFs) within a background interaction network. The key idea underlying RegLinker is the use of regular-language constraints to control the number of non-pathway edges present in the computed paths. We systematically evaluate RegLinker and alternative approaches against a comprehensive set of 15 signaling pathways and demonstrate that RegLinker exhibits superior recovery of withheld pathway proteins and interactions. These results show the promise of our approach for prioritizing candidates for experimental study and the broader potential of automated analysis to attenuate difficulties of traditional manual inquiry. / Master of Science / Cells in the human body are constantly receiving signals that inform their response to a variety of conditions. These signals serve as cues to a cell, allowing it to make informed decisions that impact cellular processes such as movement, growth, and death. Cells employ proteins and the interactions between them to achieve these capabilities. Signals manifest as molecules that interact with proteins bound to membrane of a cell. When this happens, a cascade of interactions between the proteins inside the cell will be set off. Ultimately, this cascade activate or inhibit the cell’s production of new proteins, constituting a response to the signal received. The proteins and interactions involved in such a cascade together form what is known as a signaling pathway. Experiments have uncovered the interactions that are present in many signaling pathways, and researchers have carefully cataloged this information in publicly available databases. However, high-quality curation is slow and painstaking, and many known interactions have not been annotated as belonging to any pathway. A natural question that arises is whether or not it is possible to leverage existing annotations to automatically determine which new interactions to include in a given pathway. In this thesis, we present an efficient algorithm, RegLinker, for this purpose. We evaluate this method and alternative approaches on a comprehensive set of 15 signaling pathways and demonstrate that RegLinker is better at recovering interactions withheld from these pathways. In particular, we show RegLinker’s superior ability to identify interactions that utilize proteins that were not previously considered part of a pathway. These results underscore the promise of our approach for prioritizing candidates for experimental study and the broader potential of automated analysis to attenuate difficulties of traditional manual inquiry.

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.

This dissertation considers a subclass of sum-of-ratios fractional combinatorial optimization problems (FCOPs) whose linear versions admit polynomial-time exact algorithms. This topic lies in the intersection of two scarcely researched areas of fractional programming (FP): sum-of-ratios FP and combinatorial FP. Although not extensively researched, the sum-of-ratios problems have a number of important practical applications in manufacturing, administration, transportation, data mining, etc. Since even in such a restricted research domain the problems are numerous, the main focus of this dissertation is a mathematical programming study of the three, probably, most classical FCOPs: Minimum Multiple Ratio Spanning Tree (MMRST), Minimum Multiple Ratio Path (MMRP) and Minimum Multiple Ratio Cycle (MMRC). The first two problems are studied in detail, while for the other one only the theoretical complexity issues are addressed. The dissertation emphasizes developing solution methodologies for the considered family of fractional programs. The main contributions include: (i) worst-case complexity results for the MMRP and MMRC problems; (ii) mixed 0-1 formulations for the MMRST and MMRC problems; (iii) a global optimization approach for the MMRST problem that extends an existing method for the special case of the sum of two ratios; (iv) new polynomially computable bounds on the optimal objective value of the considered class of FCOPs, as well as the feasible region reduction techniques based on these bounds; (v) an efficient heuristic approach; and, (vi) a generic global optimization approach for the considered class of FCOPs. Finally, extensive computational experiments are carried out to benchmark performance of the suggested solution techniques. The results confirm that the suggested global optimization algorithms generally outperform the conventional mixed 0{1 programming technique on larger problem instances. The developed heuristic approach shows the best run time, and delivers near-optimal solutions in most cases.

Traffic congestion has been cited as the most conspicuous problem in traffic management. It has far-reaching economic,social and political effects. Intelligent Transportation Systems (ITS) research and development programs have been assigned the task of developing sophisticated techniques and counter-measures to reduce traffic congestion to manageable levels, and also achieve these objectives using area-wide traffic management methods. During times of traffic congestion, the traffic network in a transient, time-dynamic state, and resembles a dynamic network. In addition, in the context of ITS, the network can accurately detect such transient behavior using traffic sensors, and several other information gathering devices. In conjunction with Operations Research techniques, the time-varying traffic flows can be routed through the network in an optimal manner, based on the feedback from these information sources. Dynamic Traffic Assignment (DTA) methods have been proposed to perform this task. An important step in DTA is the calculation of user-optimal, system-optimal, and multiple optimal routes for assigning traffic. One would also require the calculation of user-optimal paths for vehicle scheduling and dispatching problems. The main objective of this research study is to analyze the effectiveness of time-dependent shortest path (TDSP) algorithms and k-shortest path (k-SP) algorithms as a practical routing tool in such intelligent transportation networks. Similar algorithms have been used to solve routing problems in computer networks. The similarities and differences between computer and ITS road networks are studied. An exhaustive review of TDSP and k-SP algorithms was conducted to classify and determine the best algorithms and implementation procedures available in the literature. A new (heuristic) algorithm (TD-kSP) that calculates multiple optimal paths for dynamic networks is proposed and developed. A complete object-oriented computer program in C++ was written using specialized network representations, node-renumbering schemes and efficient path processing data structures (classes) to implement this algorithm. A software environment where such optimization algorithms can be applied in practice was then developed using object-oriented design methodology. Extensive statistical and regression analysis tests for various random network sizes, densities and other parameters were conducted to determine the computational efficiency of the algorithm. Finally, the algorithm was incorporated within the GIS-based Wide-Area Incident Management Software System (WAIMSS) developed at the Center for Transportation Research, Virginia Tech. The results of these tests are used to obtain the empirical time-complexity of the algorithm. Results indicate that the performance of this algorithm is comparable to the best TDSP algorithms available in the literature, and strongly encourages its possible application in real-time applications. Complete testing of the algorithm requires the use of real-time link flow data. While the use of randomly generated data and delay functions in this study may not significantly affect its computational performance, other measures of effectiveness as a routing tool remains untested. This can be verified only if the algorithm itself becomes a part of the user-behavior feedback loop. A closed loop traffic simulation/ system-dynamics study would be required to perform this task. On the other hand, an open-loop simulation would suffice for vehicle scheduling/dispatching problems. / Master of Science

Το πρόβλημα εύρεσης συντομότερης διαδρομής είναι ένα από τα πιο θεμελιώδη προβλήματα μονοκριτηριακής βελτιστοποίησης σε δίκτυα. Σε πολλές εφαρμογές ωστόσο, μας ενδιαφέρουν περισσότερα από ένα κριτήρια προς βελτιστοποίηση. Για παράδειγμα, στην δρομολόγηση σε ένα οδικό δίκτυο με διόδια, μας ενδιαφέρει ταυτόχρονα η ελαχιστοποίηση του χρόνου και του κόστους σε χρήματα. Παρόμοια παραδείγματα βρίσκουμε και στον χώρο των δικτύων τηλεπικοινωνιών, όπου εξετάζονται κριτήρια όπως η καθυστέρηση, η πιθανότητα λάθους, ο αριθμός συνδέσμων και άλλα. Σε αυτές οι περιπτώσεις η ``καλύτερη\\\\ / 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.

In 1985, Moffat-Takaoka (MT) algorithm was developed to solve the all pairs shortest path (APSP) problem. This algorithm manages to get time complexity of O(n² log n) expected time when the end-point independent model of probabilistic assumption is used. However, the use of a critical point introduced in this algorithm has made the implementation of this algorithm quite complicated and the running time of this algorithm is difficult to analyze. Therefore, this study introduces a new deterministic algorithm for the APSP that provides an alternative to the existing MT algorithm. The major advantages of this approach compared to the MT algorithm are its simplicity, intuitive appeal and ease of analysis. Moreover, the algorithm was shown to be efficient as the expected running time is the same O(n² log n). Performance of a good algorithm depends on the data structure used to speed up the operations needed by the algorithm such as insert, delete-min and decrease-key operations. In this study, two new data structures have been implemented, namely quaternary and dimensional heaps. In the experiment carried out, the quaternary heap that employed similar concept with the trinomial heap with a special insertion cache function performed better than the trinomial heap when the number of n vertices was small. Likewise, the dimensional heap data structure executed the decrease-key operation efficiently by maintaining the thinnest structure possible through the use of thin and thick edges, far surpassing the existing binary, Fibonacci and 2-3 heaps data structures when a special acyclic graph was used. Taken together all these promising findings, a new improved algorithm running on a good data structure can be implemented to enhance the computing accuracy and speed of todays computing machines.

Many variations of algorithms for finding the shortest path in a large graph have been introduced recently due to the needs of applications like the Geographic Information System (GIS) or Intelligent Transportation System (ITS). The primary subjects of those algorithms are materialization and hierarchical path views. Some studies focus on the materialization and sacrifice the pre-computational costs and storage costs for faster computation of a query. Other studies focus on the shortest-path algorithm, which has less pre-computation and storage but takes more time to compute the shortest path. The main objective of this thesis is to accelerate the computation time for the shortest-path queries while keeping the degree of materialization as low as possible. This thesis explores two different categories: 1) the reduction of the I/O-costs for multiple queries, and 2) the reduction of search spaces in a graph. The thesis proposes two simple algorithms to reduce the I/O-costs, especially for multiple queries. To tackle the problem of reducing search spaces, we give two different levels of materializations, namely, the <i>boundary set distance matrix</i> and <i>x-Hop sketch graph</i>, both of which materialize the shortest-path view of the boundary nodes in a partitioned graph. Our experiments show that a combination of the suggested solutions for 1) and 2) performs better than the original Disk-based SP algorithm [7], on which our work is based, and requires much less storage than <i>HEPV</i> [3].