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.

ARARUMA Arthur Rodrigues. Caminho mínimo com restrição probabilística de atraso máximo. 2013. 89 f. Dissertação (Mestrado em ciência da computação)- Universidade Federal do Ceará, Fortaleza-CE, 2013. / Submitted by Elineudson Ribeiro (elineudsonr@gmail.com) on 2016-07-08T19:26:26Z No. of bitstreams: 1 2013_dis_arararuna.pdf: 2167566 bytes, checksum: cd1f84fd0b24a51bd2b955d8e18a7ea1 (MD5) / Approved for entry into archive by Rocilda Sales (rocilda@ufc.br) on 2016-07-13T13:35:18Z (GMT) No. of bitstreams: 1 2013_dis_arararuna.pdf: 2167566 bytes, checksum: cd1f84fd0b24a51bd2b955d8e18a7ea1 (MD5) / Made available in DSpace on 2016-07-13T13:35:18Z (GMT). No. of bitstreams: 1 2013_dis_arararuna.pdf: 2167566 bytes, checksum: cd1f84fd0b24a51bd2b955d8e18a7ea1 (MD5) Previous issue date: 2013 / In the Probabilistic Delay Constrained Shortest Path problem we aim to consider the time factor in the design of cargo routing paths in road networks at minimum cost, considering the increasing uncertainty in travel times of these routes in real networks, and keeping in mind strategies of quality of service, in order to obtain a compromise between the travel costs and the compliance of the arrival time at the destination. We conducted a study of related problems in the literature of transport networks optimization, in order to better understand the problem to be addressed, about which we are not aware of existing works. We developed a scheme for enumerating partitions of the solution space of this problem, which uses an L decomposition to select these partitions wisely, and is aided by solutions to relaxations of the problem to obtain bounds for the optimal cost. In addition, we developed some branching and pruning strategies for a Branch-and-Bound scheme, with a pre-processing phase, in order to try and solve the problem directly. The computational results show that we are competitive with the commercial tool used for comparison in the smaller instances. For the remaining instances, this tool is more efficient in the time required for solving the problem. / No problema do Caminho Mínimo com Restrição Probabilística de Atraso Máximo visamos considerar o fator tempo no projeto de rotas de transporte de cargas em malhas viárias a custo mínimo, atentando à crescente incerteza nos tempos de percurso dessas rotas em malhas reais, e observá-lo tendo em mente estratégias de qualidade de serviço, de forma a obtermos um compromisso entre o custo de percurso e a conformidade ao prazo de chegada ao destino. Realizamos um estudo de problemas relacionados na literatura da área de otimização em redes de transporte, de forma a tentarmos conhecer melhor o problema a ser estudado, sobre o qual não tomamos conhecimento de trabalhos existentes. Desenvolvemos um esquema para enumeração de partições do espaço de soluções do problema, que utiliza uma decomposição em L para selecionar partições de forma inteligente, e que é auxiliado por soluções de relaxações do problema de forma a obter cotas para o custo ótimo. Além disso, desenvolvemos algumas estratégias de ramificação e de poda para um esquema de Branch-and-Bound, com uma fase de pré-processamento, de forma a tentar resolver o problema diretamente. Os resultados computacionais obtidos demonstram que somos competitivos com a ferramenta comercial utilizada para comparação em instâncias de menor porte para o problema. Para as demais instâncias, essa ferramenta se mostrou mais eficiente quanto ao tempo necessário para a resolução.

ARARUNA, Arthur Rodrigues. Caminho mínimo com restrição probabilística de atraso máximo. 2013. 88 f. : Dissertação (mestrado) - Universidade Federal do Ceará, Centro de Ciências, Departamento de Computação, Fortaleza-CE, 2013. / Submitted by guaracy araujo (guaraa3355@gmail.com) on 2016-06-01T19:53:59Z No. of bitstreams: 1 2013_dis_arararuna.pdf: 2167566 bytes, checksum: cd1f84fd0b24a51bd2b955d8e18a7ea1 (MD5) / Approved for entry into archive by guaracy araujo (guaraa3355@gmail.com) on 2016-06-01T19:54:22Z (GMT) No. of bitstreams: 1 2013_dis_arararuna.pdf: 2167566 bytes, checksum: cd1f84fd0b24a51bd2b955d8e18a7ea1 (MD5) / Made available in DSpace on 2016-06-01T19:54:22Z (GMT). No. of bitstreams: 1 2013_dis_arararuna.pdf: 2167566 bytes, checksum: cd1f84fd0b24a51bd2b955d8e18a7ea1 (MD5) Previous issue date: 2013 / In the Probabilistic Delay Constrained Shortest Path problem we aim to consider the time factor in the design of cargo routing paths in road networks at minimum cost, considering the increasing uncertainty in travel times of these routes in real networks, and keeping in mind strategies of quality of service, in order to obtain a compromise between the travel costs and the compliance of the arrival time at the destination. We conducted a study of related problems in the literature of transport networks optimization, in order to better understand the problem to be addressed, about which we are not aware of existing works. We developed a scheme for enumerating partitions of the solution space of this problem, which uses an L decomposition to select these partitions wisely, and is aided by solutions to relaxations of the problem to obtain bounds for the optimal cost. In addition, we developed some branching and pruning strategies for a Branch-and-Bound scheme, with a pre-processing phase, in order to try and solve the problem directly. The computational results show that we are competitive with the commercial tool used for comparison in the smaller instances. For the remaining instances, this tool is more efficient in the time required for solving the problem. / No problema do Caminho Mínimo com Restrição Probabilística de Atraso Máximo visamos considerar o fator tempo no projeto de rotas de transporte de cargas em malhas viárias a custo mínimo, atentando à crescente incerteza nos tempos de percurso dessas rotas em malhas reais, e observá-lo tendo em mente estratégias de qualidade de serviço, de forma a obtermos um compromisso entre o custo de percurso e a conformidade ao prazo de chegada ao destino. Realizamos um estudo de problemas relacionados na literatura da área de otimização em redes de transporte, de forma a tentarmos conhecer melhor o problema a ser estudado, sobre o qual não tomamos conhecimento de trabalhos existentes. Desenvolvemos um esquema para enumeração de partições do espaço de soluções do problema, que utiliza uma decomposição em L para selecionar partições de forma inteligente, e que é auxiliado por soluções de relaxações do problema de forma a obter cotas para o custo ótimo. Além disso, desenvolvemos algumas estratégias de ramificação e de poda para um esquema de Branch-and-Bound, com uma fase de pré-processamento, de forma a tentar resolver o problema diretamente. Os resultados computacionais obtidos demonstram que somos competitivos com a ferramenta comercial utilizada para comparação em instâncias de menor porte para o problema. Para as demais instâncias, essa ferramenta se mostrou mais eficiente quanto ao tempo necessário para a resolução.