A*(A-Star)演算法透過啟發函式，以減少路徑搜尋過程中所需要計算的網路數量，SMA*(Simplified Memory Bounded A-Star)為A*之變形，目前最廣泛被應用於GPS導航系統之路徑規劃的演算法。尋找路徑的計算過程中，A*與SMA*演算法利用中間節點與目的地的方向(直線距離)作為啟發函式，以預估中間節點到目的地之路徑長度挑選優先搜尋的路段，而SMA*則因記憶體的限制會排除預估長度較長的路段，以減少搜尋的路段數量與記憶體之使用量。當起點與終點中存在障礙地形時或路段較崎嶇時，以方向導引路徑搜尋之準確度便大幅降低，導致A*與SMA*之搜尋數量增加，SMA*甚至會得到較差的路徑。 主幹導引式最短路徑搜尋演算法(Backbone Orientation)以骨幹路徑導引路徑之搜尋，在障礙地形或道路崎嶇的情況下，可有效避免SMA*之缺點，效能較佳。主幹導引式最短路徑搜尋演算法分為二階段，先由原始路網中提取骨幹路網，並計算出最佳骨幹路徑，再利用骨幹路徑引導路徑的搜尋，在骨幹路徑的一定範圍內搜尋最短路徑。 本研究以台灣地區2007年之平面路網圖進行實驗，以三種不同的實驗方式進行實驗，以驗證主幹導引式最短路徑搜尋演算法之效能，證明在SMA*演算法之啟發函式效能低落時，使用主幹導引式最短路徑搜尋演算法可以有效的改善SMA*在障礙地形之效能不彰的問題。

Efficient energy use is primarily for any sensor networks to function for a longer time period. There have been many efficient schemes with various progress levels proposed by many researchers. Yet, there still more improvements are needed. This thesis is an attempt to make wireless sensor networks with further efficient on energy usage in the network with respect to rate of delivery of the messages. In sensor network architecture radio, sensing and actuators have influence over the power consumption in the entire network. While listening as well as transmitting, energy is consumed by the radio. However, if by reducing listening times or by reducing the number of messages transmitting would reduce the energy consumption. But, in real time scenario with critical information sensing network leads to information loss. To overcome this an adaptive routing technique should be considered. So, that it focuses on saving energy in a much more sophisticated way without reducing the performance of the sensing network transmitting and receiving functionalities. This thesis tackles on parts of the energy efficiency problem in a wireless sensor network and improving delivery rate of messages. To achieve this a routing technique is proposed. In this method, switching between two routing paths are considered and the switching decision taken by the server based on messages delivered comparative previous time intervals. The goal is to get maximum network life time without degrading the number of messages at the server. In this work some conventional routing methods are considered for implementing an approach. This approach is by implementing a shortest path, Gradient based energy routing algorithm and an observer component to control switching between paths. Further, controlled switching done by observer compared to normal initial switch rule. Evaluations are done in a simulation environment and results show improvement in network lifetime in a much more balanced way.

[pt] A interpretação manual de um horizonte sísmico é um processo muito custoso em termos de tempo de trabalho do intérprete, o que incentiva a pesquisa de métodos automáticos, ou semi automáticos, de rastreamento. Dentre as propostas existentes baseadas em correlação, uma limitação conhecida é o uso de abordagens locais para definir as amostras pertencentes ao horizonte rastreado. Esse tipo de abordagem possui bom desempenho em dados onde não há a presença de falhas sísmicas, porém, nas regiões de baixa coerência, característica das regiões ruidosas ou de falhas, ao tomar uma decisão local o rastreador fica suscetível à propagação de erro. O objetivo deste trabalho é avaliar o uso de algoritmos de menor caminho em grafos para a solução do problema de rastreamento de horizontes sísmicos, afim de propor um método de caráter global que seja robusto a diferentes feições sísmicas. / [en] The manual interpretation of a seismic horizon is a time consuming process, which drives the research for automatic or semi automatic tracking methods. Among the known propositions that use correlation, there is a common limitation: the usage of local approaches to determine which samples belong to the horizon. This kind of approach performs well in data where there are no seismi faults. However, by using only local information, it is prone to error propagation in low coherency areas, which usualy corresponds to fault regions. The goal of this work is to evaluate the performance of shortest path algorithms as a solution for the horizont tracking problem. It intends to propose a global method that is robust to different seismic features.

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.

Este trabalho apresenta um estudo teórico da Técnica de Geração de Colunas (GC) aplicada em alguns Problemas de Roteamento de Veículo (PRV). Essa técnica foi inicialmente utilizada para tratar problemas de otimização de grande porte com estruturas especiais[Dantzig & Wolfe, 1960]. Dentre as diversas classes de problemas de roteamento; revisamos a aplicação dessa técnica a dois casos particulares: O problema de roteamento de helicópteros em plataformas marítimas, cujo objetivo minimizar o custo total do transporte; O problema de roteamento com janela de tempo, onde a função objetivo é descrita pelo tamanho da frota e o custo do percurso. Revisamos e implementamos um algoritmo de caminho mínimo com janela de tempo (CMJT). Esse algoritmo surge como um sub-problema do algoritmo Primai Simplex para resolver o problema de partição de conjunto, utilizado para modelar o problema de roteamento com janela de tempo. / This work presents a study about the Column Generation Technique (CG) applied to some Vehicle Ftouting Problems. The technique was first used to deal with optimization problems having special structures. Among the vaa-ious classes of routing problems, we review the use of the technique in two specific cases: Ftouting helicopters for crew exchanges on off-shore locations, where the objective is to minimize the total transportation cost; Ftouting with time windows, where the objective function is composed by the size of the fleet and the cost of route. We review and implement a shortest path algorithm with time windows. This algorithm aa-ises as a sub-problem in the Primai Simplex algorithm to solve the linear relaxation of the set partitioning problem used to model the routing problem with time windows.

Este trabalho apresenta um estudo teórico da Técnica de Geração de Colunas (GC) aplicada em alguns Problemas de Roteamento de Veículo (PRV). Essa técnica foi inicialmente utilizada para tratar problemas de otimização de grande porte com estruturas especiais[Dantzig & Wolfe, 1960]. Dentre as diversas classes de problemas de roteamento; revisamos a aplicação dessa técnica a dois casos particulares: O problema de roteamento de helicópteros em plataformas marítimas, cujo objetivo minimizar o custo total do transporte; O problema de roteamento com janela de tempo, onde a função objetivo é descrita pelo tamanho da frota e o custo do percurso. Revisamos e implementamos um algoritmo de caminho mínimo com janela de tempo (CMJT). Esse algoritmo surge como um sub-problema do algoritmo Primai Simplex para resolver o problema de partição de conjunto, utilizado para modelar o problema de roteamento com janela de tempo. / This work presents a study about the Column Generation Technique (CG) applied to some Vehicle Ftouting Problems. The technique was first used to deal with optimization problems having special structures. Among the vaa-ious classes of routing problems, we review the use of the technique in two specific cases: Ftouting helicopters for crew exchanges on off-shore locations, where the objective is to minimize the total transportation cost; Ftouting with time windows, where the objective function is composed by the size of the fleet and the cost of route. We review and implement a shortest path algorithm with time windows. This algorithm aa-ises as a sub-problem in the Primai Simplex algorithm to solve the linear relaxation of the set partitioning problem used to model the routing problem with time windows.

Avec les problèmes présents dans le secteur de transport, qu'ils soient financiers ou environnementaux, la mobilité avancée peut y remédier avec la mise à profit de la complémentarité entre les différents modes de transport. Dans ce contexte, nous nous focalisons dans cette thèse à la mise en œuvre d'un système d’information de transport avec la recherche et la composition des itinéraires comodaux pour les clients. L'enjeu est d'être capable de répondre aux attentes des usagers avec des solutions satisfaisantes permettant de proposer des itinéraires optimaux pour gérer efficacement l’intermodalité. Dans un souci pratique, nous fournirons des itinéraires attractifs respectant les contraintes imposées même pour les requêtes simultanées. Nous utilisons des techniques d'accélération permettant de réduire l'espace de recherche pour la planification d’itinéraire. Les itinéraires attractifs sont décomposés en sections de route sur lesquelles les différentes demandes et les offres disponibles sont mises en relation. Les combinaisons des sections de route permettent d'aboutir à un ensemble de solutions intéressantes. L’aspect distribué et dynamique du problème nous a permis d'employer une modélisation basée sur le paradigme agent. Ainsi, l’alliance entre les systèmes multi-agents et les algorithmes génétiques que nous avons mis en place s'avère très utile pour gérer l’articulation de l’intermodalité entre ces différents modes de transport. Les résultats de simulation présentés montrent l’efficacité des méthodes proposées. / Nowadays, the environment impact of transport is significant. In an attempt to address these problems, in this work, we are interested in the implementation of a transport information system, which integrates the existing means of transport to respond users' requests, including public transport and the shared transport like carpooling and car-sharing. In this context of application, we elaborate algorithms to provide attractive paths with respect to the imposed constraints, even for simultaneous requests. Different acceleration techniques for path planning are used to reduce the search space for a better performance. The attractive paths are divided into route sections on which the available offers are allocated to different requests, which is treated as one resource allocation problem using metaheuristics algorithms. With consideration of the distributed and dynamic aspects of the problem, the solving strategy makes use of several concepts like multi-agents system and different optimization methods. The proposed methods are tested with realistic scenarios with instances extracted from real world transport networks. The obtained results indicate that our proposed approaches can efficiently solve the itinerary planning problems by providing good and complete solutions.

<p>Traffic planning in a modern congested society is an important and time consuming procedure. Finding fast algorithms for solving traffic problems is therefore of great interest for traffic planners allover the world. </p><p>This thesis concerns solving the fixed demand traffic assignment problem (TAP) on a number of different transportation test networks. TAP is solved using the Frank-Wolfe algorithm and the shortest path problems that arise as subproblems to the Frank-Wolfe algorithm are solved using the network simplex algorithm. We evaluate how a number of existing pricing strategies to the network simplex algorithm performs with TAP. We also construct a new efficient pricing strategy, the Bucket Pricing Strategy, inspired by the heap implementation of Dijkstra's method for shortest path problems. This pricing strategy is, together with the actual use of the network simplex algorithm, the main result of the thesis and the pricing strategy is designed to take advantage of the special structure of TAP. In addition to performing tests on the conventional Frank-Wolfe algorithm, we also test how the different pricing strategies perform on Frank-Wolfe algorithms using conjugate and bi-conjugate search directions. </p><p>These test results show that the updating shortest path calculations obtained by using the network simplex outperforms the non-updating Frank-Wolfe algorithms. Comparisons with Bar-Gera's OBA show that our implementation, especially together with the bucket pricing strategy, also outperforms this algorithm for relative gaps down to 10E-6.</p>

Empirical studies show that similar patterns emerge from a large number of different biological systems. For example, the group size distributions of several fish species and house sparrows all follow power law distributions with an exponential truncation. Networks built by ant colonies, slime mold and those are designed by engineers resemble each other in terms of structure and transportation efficiency. Based on the investigation of experimental data, we propose a variety of simple stochastic models to unravel the underlying mechanisms which lead to the collective phenomena in different systems. All the mechanisms employed in these models are rooted in the concept of selective reinforcement. In some systems the reinforcement can build optimal solutions for biological problem solving. This thesis consists of five papers. In the first three papers, I collaborate with biologists to look into group formation in house sparrows  and the movement decisions of damsel fish.  In the last two articles, I look at how shortest paths and networks are  constructed by slime molds and pheromone laying ants, as well as studying  speed-accuracy tradeoffs in slime molds' decision making. The general goal of the study is to better understand how macro level patterns and behaviors emerges from micro level interactions in both spatial and non-spatial biological systems. With the combination of mathematical modeling and experimentation, we are able to reproduce the macro level patterns in the studied biological systems and predict behaviors of the systems using minimum number of parameters.

No description available.