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.

A framework is proposed for determining the least expected cost path in a schedule-based time-expanded public transit network where travel times, and thus bus arrival and departure times at stops, are stochastic. Transfer reliability is incorporated in a label-correcting algorithm with a penalty function for the expected waiting time when transferring that reflects the likelihood of making a successful transfer. The algorithm is implemented in transit assignment on an Austin, Texas test network, using actual bus arrival and departure time distributions from vehicle location data. Assignment results are compared with those of a deterministic shortest path based on the schedule and from a calibrated transit assignment model. Simulations of the network and passenger paths are also conducted to evaluate the overall path reliability. The reliable shortest path algorithm is found to penalize transferring and provide paths with improved transfer and overall reliability. The proposed model is realistic, incorporating reliability measures from vehicle location data, and practical, given the efficient shortest path approach and application to transit assignment. / text

Traffic congestion has been imposing a tremendous burden on society as a whole. For decades, the most widely applied solution has been building more roads to better accommodate traffic demand, which turns out to be of limited effect. Active Traffic and Demand Management (ATDM) is getting more attention recently and is considered here, as it leverages market-ready technologies and innovative operational approaches to manage traffic congestion within the existing infrastructure. The key to a successful Active Traffic and Demand Management strategy is to effectively induce travelers' behavior to change. In spite of the increased attention and application throughout the U.S. or even the world, most ATDM strategies were implemented on-site through small-scale pilot studies. A systematic framework for analysis and evaluation of such a system in order to effectively track the changes in travelers' behavior and the benefit brought about by such changes has not been established; nor has the effect of its strategies been quantitatively evaluated. In order to effectively evaluate the system benefit and to analyze the behavior changes quantitatively, a systematic framework capable of supporting both macroscopic and microscopic analysis should be established. Such system should be carefully calibrated to reflect the traffic condition in reality, as only after the calibration can the baseline model be used as the foundation for other scenarios in which alternative design or management strategies are incorporated, so that the behavior changes and system benefit can be computed accurately by comparing the alternative scenarios with the baseline scenario. Any effective traffic management strategy would be impossible if the traveler route choice behavior in the urban traffic network has not been fully understood. Theoretical research assumes all users are homogeneous in their route choice decision and will always pick the route with the shortest travel cost, which is not necessarily the case in reality. Researchers in Minnesota found that only 34% of drivers strictly traveled on the shortest path. Drivers' decision is made usually based on several dimensions, and a full understanding of the travel route choice behavior in the urban traffic network is essential. The existence of most current Advanced Traveler Information Systems (ATIS) offer the capability to provide pre-trip and/or en route real time information, allowing travelers to quickly assess and react to unfolding traffic conditions. The basic design concept is to present generic information to drivers, leaving drivers to react to the information their own way. This "passive" way of managing traffic by providing generic traffic information has difficulty in predicting outcome and may even incur adverse effect, such as overreaction (aka herding effects). Furthermore, other questions remain on how to utilize the real-time information better and guide the traffic flow more effectively towards a better solution, and most current research fails to take the traveler's external cost into consideration. Motivated by those concerns, in this research, a behaviorally induced system optimal model is presented, aimed at further improving the system-level traffic condition towards System Optimal through incremental routing, as well as establishing the analysis methodology and evaluation framework to calibrate quantitatively the behavior change and the system benefits. In this process, the traffic models involved are carefully calibrated, first using a two-stage calibration model which is capable of matching not only the traffic counts, but also the time dependent speed profiles of the calibrated links. To the best of our knowledge, this research is the first with a methodology to incorporate the use of field observed data to estimate the Origin-Destination (OD) matrices departure profile. Also proposed in this dissertation is a Constrained K Shortest Paths algorithm (CKSP) that addresses route overlap and travel time deviation issues. This proposed algorithm can generate K Shortest Paths between two given nodes and provide sound route options to the drivers in order to assist their route choice decision process. Thirdly, a behaviorally induced system optimal model includes the development of a marginal cost calculation algorithm, a time-dependent shortest path search algorithm, and schedule delay as well as optimal path finding models, is present to improve the traffic flow from an initial traffic condition which could be User Equilibrium (UE) or any other non-UE or non-System-Optimal (SO) condition towards System Optimal. Case studies are conducted for each individual research and show a rather promising result. The goal of establishing this framework is to better capture and evaluate the effects of behaviorally induced system optimal traffic management strategies on the overall system performance. To realize this goal, the three research models are integrated in order to constitute a comprehensive platform that is not only capable of effectively guiding the traffic flow improvement towards System Optimal, but also capable of accurately evaluating the system benefit from the macroscopic perspective and quantitatively analyzing the behavior changes microscopically. The comprehensive case study on the traffic network in Tucson, Arizona, has been conducted using DynusT (Dynamic Urban Simulation for Transportation) Dynamic Traffic Assignment (DTA) simulation software; the outcome of this study shows that our proposed modeling framework is promising for improving network traffic condition towards System Optimal, resulting in a vast amount of economic saving.

The transportation routing map is increasingly used in various transportation network modeling applications such as vehicle navigation and traffic assignment modeling. A typical navigation GIS map contains all detailed road facility layers and may not be as computationally efficient as a lower-resolution map for path finding. A lower-resolution transportation routing map retains only route-finding related roadways and is efficient for path finding but may result in sub-optimal routes because of misclassification links. With the goal in balancing the traffic analysis requirement of intended application and computation requirements of transportation navigation and traffic assignment, the systematic abstraction of the lower-resolution transportation routing map from high resolution map is an important and non-trivial task. For vehicle navigation applications, the traffic analysis requirement is the shortest path quality. An innovative transportation routing map abstraction method or Connectivity Enhancement Algorithm (CEA) is proposed to deal with vehicle navigation application routing map abstraction. The algorithm starts from a low-resolution network and keeps updating the map by adding links and nodes when it processes each search set. The outcome of the algorithm is an abstract map that retains the original detailed map's hierarchical structure with quality topological connectivity at a significant computations saving. With the development of traffic assignment modeling, a detailed network is desired to describe the real world traffic network. It is the consensus that one should not directly apply a GIS map blind-sight without a systematic approach and unnecessarily overuse the network details causes excessive run time. The traffic analysis requirement of those applications is the dynamic user equilibrium (DUE) condition network performance is identical or near-identical with high resolution network. The lowest network resolution level that meets the requirements of emerging traffic analysis is not easy to determine. The proposed traffic analysis network abstraction method gives a solution for this problem. It is an iterative network abstraction approach and considers the link travel time with DUE traffic condition. The case study and numerical analysis prove that the two network abstraction methods are sound and promising. The transportation routing map abstraction method could detect most misclassification links and is robust for different network scales. The abstracted navigation map provides the identical or near-identical SP cost/travel time for any OD pair while the computation burden is much lighter than that on original map. In another hand, the case studies about the traffic analysis network abstraction tell that the method converges very quick and the rendered the abstracted network that has lowest resolution of network or least links and nodes but the DUE condition network performance or trips cost/travel time is much closer to that on the original map.

No description available.

This thesis is divided into two parts that each is concerned with a specific problem. The problem under consideration in the first part is to find suitable graph representations, abstractions, cost measures and algorithms for calculating placements of unmanned aerial vehicles (UAVs) such that they can keep one or several static targets under constant surveillance. Each target is kept under surveillance by a surveillance UAV, which transmits information, typically real time video, to a relay UAV. The role of the relay UAV is to retransmit the information to another relay UAV, which retransmits it again to yet another UAV. This chain of retransmission continues until the information eventually reaches an operator at a base station. When there is a single target, then all Pareto-optimal solutions, i.e. all relevant compromises between quality and the number of UAVs required, can be found using an efficient new algorithm. If there are several targets, the problem becomes a variant of the Steiner tree problem and to solve this problem we adapt an existing algorithm to find an initial tree. Once it is found, we can further improve it using a new algorithm presentedin this thesis. The second problem is optimization of time-consuming problems where the objective function is seen as a black box, where the input parameters are sent and a function valueis returned. This has the important implication that no gradient or Hessian information is available. Such problems are common when simulators are used to perform advanced calculations such as crash test simulations of cars, dynamic multibody simulations etc. It is common that a single function evaluation takes several hours. Algorithms for solving such problems can be broadly divided into direct search algorithms and model building algorithms. The first kind evaluates the objective function directly, whereas the second kind builds a model of the objective function, which is then optimized in order to find a new point where it is believed that objective function has agood value. Then the objective function is evaluated in that point. Since the objective function is very time-consuming, it is common to focus on minimizing the number of function evaluations. However, this completely disregards the possibility to perform calculations in parallel and to exploit this we investigate different ways parallelization can be used in model-building algorithms. Some of the ways to do this is to use several starting points, generate several new points in each iteration, new ways of predicting a point’s value and more. We have implemented the parallel extensions in one of the state of the art algorithms for derivative-free optimization and report results from testing on synthetic benchmarksas well as from solving real industrial problems.

Network analysis in GIS is often related to finding solutions to transportation problems. In a GIS the real world is represented by either one of two spatial models, vector-based, or raster-based. Prefering raster or vector GIS is more a question of choice than of accuracy. A raster-based GIS model shows a better fit, when the problem is concerned with finding a path across terrain which does not have predefined paths. The approach of this study is to translate the scenario into a &lsquo / least-cost path&rsquo / graph with an associated cost function on the raster-based GIS layer. Sometimes, computation of shortest paths between different locations on a raster-based GIS has to be done in real-time. Therefore, knowing which shortest path algorithm runs fastest on real networks is needed. In order to meet this requirement, Dijsktra&rsquo / s algorithm with priority queue implementation is selected, because it reduces the time complexity of Dijsktra&rsquo / s algorithm from O(V2 log V) to O(E log V ). The run-time results of Dijsktra&rsquo / s algorithm, Dijsktra&rsquo / s algorithm with priority queue implementation and ArcMap Spatial Analyst Tool are compared for a number of raster GIS layers which have different number of nodes. Dijsktra&rsquo / s algorithm with priority queue implementation and Spatial Analyst tool of ArcMap show a linear relationship between node numbers and time, whereas Dijsktra&rsquo / s algorithm represents a quadratic relationship. Hence, when the number of nodes and edges in graph is increased, the run-time performance of the Dijsktra&rsquo / s algorithm decreases rapidly.

In a peer-to-peer shared ride system, transportation clients with traffic demand negotiate with transportation hosts offering shared ride services for ad-hoc ridesharing in a continuously changing environment, using wireless geosensor networks. Due to the distinctive characteristic of this system—a complex and non-deterministic transportation network, and a local peer-to-peer communication strategy—clients will always have limited transportation knowledge, both from a spatial and a temporal perspective. Clients hear only from nearby hosts, and they do not know the future availability of current or new hosts. Clients can plan optimal trips prior to departure according to their current knowledge, but it is unlikely that these trips will be final optimal trip due to continuously changing traffic conditions. Therefore, it is necessary to evaluate the trip quality in this dynamic environment in order to assess different communication and wayfinding strategies. (For complete abstract open document)

Thesis (M.S.)--Brigham Young University. Dept. of Computer Science, 2005. / Includes bibliographical references (p. 59-62).

Το πρόβλημα εύρεσης συντομότερων διαδρομών είναι ένα από τα πιο θεμελιώδη προβλήματα μονοκριτηριακής βελτιστοποίησης σε δίκτυα. Σε αυτό το πρόβλημα αναζητείται η συντομότερη διαδρομή μεταξύ δύο δεδομένων σημείων ελαχιστοποιώντας ένα κριτήριο κόστους. Σε πολλές εφαρμογές ωστόσο, μας ενδιαφέρουν περισσότερα από ένα κριτήρια προς βελτιστοποίηση. Για παράδειγμα, στην εύρεση διαδρομών σε ένα οδικό δίκτυο με διόδια, μας ενδιαφέρει εκτός από την διανυμένη απόσταση και η ελαχιστοποίηση του χρόνου και του κόστους. Παρόμοια παραδείγματα βρίσκουμε και στον χώρο των δικτύων τηλεπικοινωνιών, όπου εξετάζονται κριτήρια όπως η καθυστέρηση, η πιθανότητα λάθους, ο αριθμός συνδέσμων και άλλα. Σε αυτές τις περιπτώσεις η καλύτερη λύση δεν μπορεί να οριστεί με μονοσήμαντο τρόπο, και συνεπώς καταφεύγουμε σε αντισταθμίσεις μεταξύ των παραγόντων, που είναι γνωστές ως σύνολο λύσεων κατά Pareto. Παρόλο που για το πρόβλημα μονοκριτηριακής εύρεσης συντομότερων διαδρομών υπάρχουν πολλοί αποδοτικοί αλγόριθμοι για την επίλυση του προβλήματος, το αντίστοιχο πολυκριτηριακό πρόβλημα είναι πολύ πιο σύνθετο. Μέχρι τώρα, αυτό το πρόβλημα έχει αποδειχθεί ότι είναι NP-πλήρες. Επιπλέον, έχει αποδειχθεί ότι το πλήθος των λύσεων σε αυτό το πρόβλημα αυξάνεται εκθετικά σε σχέση με το μέγεθος της εισόδου. Υπάρχουν δύο βασικές προσεγγίσεις επίλυσης τέτοιων προβλημάτων, όπου εξετάζονται πολλαπλά κριτήρια. α) Η πρώτη μέθοδος βρίσκει προσεγγιστικές λύσης κατά έναν ορισμένο παράγοντα. Οι προσεγγιστικές μέθοδοι δεν βρίσκουν απαραίτητα ακριβείς λύσεις, αλλά είναι σχετικά γρήγορες και προσφέρουν εγγύηση για το ποσοστό απόκλισης από την βέλτιστη λύση. β) Η δεύτερη μέθοδος χρησιμοποιεί ευρετικές βελτιώσεις για να επιταχύνει τους ήδη υπάρχοντες αλγορίθμους. Τέτοιες τεχνικές βρίσκουν ακριβείς λύσεις, και το ζητούμενο είναι να επιτευχθεί μια πολύ καλή χρονική απόδοση. Στην παρούσα διπλωματική εργασία επικεντρωνόμαστε στην δεύτερη μέθοδο, υποκινούμενοι από την μεγάλη ζήτηση πρακτικών εφαρμογών για εύρεση αποτελεσματικής και ακριβούς λύσης του προβλήματος συντομότερων διαδρομών υπό πολλαπλά κριτήρια. Πιο συγκεκριμένα, στην εργασία αυτή παρουσιάζουμε ένα ενοποιημένο πλαίσιο για την αποδοτική επίλυση αυτών των προβλημάτων. Προτείνουμε νέες μεθόδους ή βελτιώσεις των υπαρχόντων. Υλοποιήσαμε τις μεθόδους που παρουσιάζουμε συνοδεύοντάς τις με μια εκτενή πειραματική μελέτη πάνω σε δίκτυα ευρείας κλίμακας. / We present new implementations of heuristic algorithms for the solution of the multiobjective shortest path problem, using a new graph structure specifically suited for large scale road networks. We enhance the heuristics with further optimizations and experimentally evaluate the performance of our enhanced implementation on real world road networks achieving 10 times better performance with respect to the best previous study.