Fuel efficiency is an ever present problem in today's modern world. The United States in particular is in need of a solution to lowering greenhouse gas emissions caused by transit and freight across its spread out cities. In fact in the United States the average commute time of an individual is 26 minutes, meaning that round trip people are driving about an hour every day, to and from work. But that gas consumption is pittiling compared to that of the freight industry. Heavy Duty Vehicles (HDVs) commonly known as semi trucks, account for three quarters of US freight emissions and 7.5% of total US greenhouse gas emissions [2]. But this can be cut down considerably with the implementation of platooning. Platooning is when multiple vehicles follow in close distance to reduce aerodynamic drag, causing significant fuel savings. In this paper, we will go over an algorithm to help vehicles join with already formed platoons on the road, increasing their fuel efficiency and therefore saving cost to the driver in addition to lessening the negative effect on the planet. This will be done using a modified A* algorithm. The base weight of zero will be the amount of gas the vehicle would consume taking the shortest path that google maps recommends, alone, with no platooning. Paths may end up with negative weights due to the fuel savings caused by joining existing platoons during the vehicles’ travel. The algorithm will have access to a map of the roadways and the GPS data of nearby platoons. It will then perform a cost-benefit analysis to determine if the fuel savings from joining a platoon will outweigh the cost of going outside of its original path in order to join the other vehicles.

Įvairūs grafo srautų minimizavimo arba maksimizavimo uždaviniai yra taikomi modeliuoti procesams logistikoje, kompiuteriniuose tinkluose, akcijų biržose, automobilių eisme ir t.t. Tokio uždavinio sprendimas esant dideliems grafams yra labai sudėtingas, todėl modelyje būna mažai kintančių parametrų arba modeliuojama tik dalis proceso. Tokio uždavinio pavyzdys (kuris ir bus nagrinėjamas) yra eismo modeliavimas keliuose. Kiekvienas vairuotojas bando pasiekti savo tikslą per minimalų galimą tuo metu esančiomis sąlygomis laiką. Tokiu būdu yra užimama „geriausia vieta“ kelyje, o kitiems vairuotojams užimtas kelias gali tapti neberacionalus ir bus pasirenkamas alternatyvus. Šioje vietoje atsispindi esminė tokio tipo uždavinio savybė: kiekvienas proceso dalyvis siekia maksimalios naudos sau, tokiu būdu tą naudą atimdamas iš kitų dalyvių. Šiu atveju „nauda“ yra vieta eisme. Darbe yra aprašytas eismo imitavimo sistemos modelis ir realizuotas tokia architektūra, kuri tinkama lygiagretiems skaičiavimams. Pateikta statistiniai gauto modelio analizavimo pavyzdžiai. Taip pat pasiūlyti keli algoritmai specifiniams uždaviniams spręsti, kaip dalinis modelio perskaičiavimas. / In this work we will try to apply various path search algorithm optimizations for solving traffic simulation problem. These optimizations are made on the basis of processes and patterns specific to car traffic. Other areas like logistics, money traffic and stocks should have their own specific optimizations. Primary selection criteria will be calculation time. Errors are also introduced by these optimizations, but benefits of solving more complex problems in much shorter time will outweigh those errors. Most of described algorithms are just modifications of traditional Dijkstra's algorithm. This allows to show step by step every optimization introduced, which we can split into 3 categories: Algorithms for finding shortest path in untouched graph, Algorithms for finding shorted path which need modified graph, Algorithms specific for traffic simulation. Algorithms up to graph transformations have been analyzed in previous works. These optimizations proved to be very perspective in point-to-point path search. Thou applying them to traffic modeling and introducing modeling specific optimizations is a relatively new research area. Also an algorithm imitating traffic laws has to be implemented. One of suggested optimizations could be called “fast partial recalculation”. This would allow a faster recalculation of main path loads. Assuming that traffic is the same and graph is slightly modified. A modified idea could be adapted for a recalculation with modified traffic loads. Vastly... [to full text]

OLIVEIRA, Erneson Alves de. Geração de fraturas autossimilares em meios desordenados: técnicas do caminho crítico e do caminho mínimo. 2008. 54 f. Dissertação (Mestrado em Física) - Programa de Pós-Graduação em Física, Departamento de Física, Centro de Ciências, Universidade Federal do Ceará, Fortaleza, 2008. / Submitted by Edvander Pires (edvanderpires@gmail.com) on 2014-11-03T20:05:53Z No. of bitstreams: 1 2008_dis_eaoliveira.pdf: 13308297 bytes, checksum: 51bfea9dc79470d1077454f8be1b593a (MD5) / Approved for entry into archive by Edvander Pires(edvanderpires@gmail.com) on 2014-11-03T20:12:15Z (GMT) No. of bitstreams: 1 2008_dis_eaoliveira.pdf: 13308297 bytes, checksum: 51bfea9dc79470d1077454f8be1b593a (MD5) / Made available in DSpace on 2014-11-03T20:12:15Z (GMT). No. of bitstreams: 1 2008_dis_eaoliveira.pdf: 13308297 bytes, checksum: 51bfea9dc79470d1077454f8be1b593a (MD5) Previous issue date: 2008 / In this work we propose two models for fracture generation in regular substrates. In the first model, we iteratively apply the concept of critical path to systematically determine the lower “conductivity” element in the connected spanning network. At each iteration, once these elements are identified as local “cracks ́ ́, they are permanently removed from the structure up to the point in which a macroscopic fracture can destroy the global network connectivity. This fracture is then topologically characterized as self-similar with fractal dimension Dp ≈ 1.21. In the second model, we employ the algorithm of Dijkstra to determine the minimal path in a random energy landscape and remove its highest energy element. As in the previous model, these elements are considered to be local “cracks ́ ́ till a subset of them can be identified as a macroscopic fracture. The average over many samples of fractures calculated for different system sizes reveals the presence of a self-similar structure with fractal dimension Df ≈ 1.21. The resemblance between the two exponents Dp e Df suggests that the two models belong to the same universality class. / Neste trabalho propomos dois modelos para a geração de fraturas em substratos regulares. No primeiro modelo, empregamos iterativamente o conceito de caminho crítico para determinar sistematicamente o elemento de menor “condutividade” da rede. Estes elementos são então identificados como “falhas” e removidos permanentemente da estrutura até que uma fratura macroscópica destrua a conectividade global da rede. Uma vez detectada, esta fratura é caracterizada topologicamente como uma estrutura auto-similar de dimensão fractal Dp ≈ 1.21. No segundo modelo, empregamos iterativamente o algoritmo de Dijkstra para determinar o caminho mínimo em uma paisagem aleatória, retirando sistematicamente desta estrutura o elemento de maior energia. Como no modelo anterior, estes elementos são identificados como “falhas” até que um conjunto conecto deles resulte em uma fratura macroscópica. A média realizada sobre várias amostras de fraturas em diferentes tamanhos de substratos revela a presença de uma estrutura auto-similar de dimensão fractal Df ≈ 1.21. A semelhança numérica entre os expoentes Dp e Df sugere que os dois modelos pertencem à mesma classe de universalidade.

ITC/USA 2012 Conference Proceedings / The Forty-Eighth Annual International Telemetering Conference and Technical Exhibition / October 22-25, 2012 / Town and Country Resort & Convention Center, San Diego, California / Spectrum efficiency is the key challenge in modern telemetry systems. Network telemetry requires moving from a dedicated link structure to a network structure which is a very complex problem and requires spectrum management tools. A mixed network structure has been previously proposed for networked telemetry which employs a combination of cellular and Adhoc networks. Significant improvements in QoS and clustering of the complex aeronautical networks have been observed and published in several venues. However in the earlier work routing within the Ad-hoc clusters has not been addressed and the clustering has been done using an enhanced K-means clustering. In this paper, a well known clustering algorithm is adopted in the mixed network concept and clustering of the Ad-hoc nodes are optimized based on shortest route to the gateway and minimum hop count criteria. The proposed clustering technique in this paper leads to a jointly optimized cluster-topology and gateway-selection solution a complex aeronautical network. Simulation results towards the end of this paper illustrate that with the proposed method, cluster configuration is locally optimized and the best gateway for each cluster is successfully selected. With addition of traffic measures to the consideration in the routing, the proposed solution will leads to efficient spectrum allocation and improved QoS.

As an alternative to the Fibonacci heap, and a variation of the 2-3 heap data structure by Tadao Takaoka, this research presents the 3-4 heap data structure. The aim is to prove that the 3-4 heap, like its counter-part 2-3 heap, also supports n insert, n delete-min, and m decrease-key operations, in O(m + nlog n) time. Many performance tests were carried out during this research comparing the 3-4 heap against the 2-3 heap and for a narrow set of circumstances the 3-4 heap outperformed the 2-3 heap. The 2-3 heap has got a structure based on dimensions which are rigid using ternary linking and this path is made up of three nodes linked together to form a trunk, and the trunk is permitted to shrink by one. If further shrinkage is required then an adjustment is made by moving a few nodes from nearby positions to ensure the heaps rigid dimensions are retained. Should this no longer be the case, then the adjustment will trigger a make-up event, which propagates to higher dimensions, and requires amortised analysis. To aid amortised analysis, the trunk is given a measurement value called potential and this is the number of comparisons required to place each node into its correct position in ascending order using linear search. The divergence of the 3-4 heap from the 2-3 heap is that the trunk maximum is increased by one to four and is still permitted to shrink by one. This modified data structure will have a wide range of applications as the data storage mechanism used by graph algorithms such as Dijkstra's 'Single Source Shortest Path'.

Den här undersökningen har jämfört ifall ett gemensamt dynamiskt flödesfält som fylls allteftersom kan prestera bättre än när varje agent måste fylla sitt eget flödesfält. Ett antal scenarion har skapats för att ta reda på vilket sätt teknikerna skiljer sig. Ett scenario utvärderas genom att automatiskt placera ut en stor mängd agenter och notera FPS under testets gång. Dessa data presenteras sedan i en gemensam graf för de två teknikerna där skiljaktigheterna går att observera. Efter testning visar det sig att de två största anledningarna till skillnaden i prestanda är beroende på storleken av agenternas sökrymd samt hur många spridda mål det finns. En stor sökrymd försämrar den icke dynamiska tekniken medan den dynamiska presterar bra. Många spridda mål försämrar den dynamiska teknikens prestanda på grund av att fältet inte kan återanvändas. Resultatet diskuteras kunna användas i en hybridlösning för vektorfält, samt kunna jämföras med ett komplett flödesfält.

De flesta algoritmer som används för ruttplanering finner en ruttmellan en start- och slutposition. Ofta handlar det om att hitta denkortaste eller snabbaste rutten mellan positionerna. Denna studie hartill syfte att ta fram en metod som hittar flera lämpliga rutter mellantvå positioner med användning av Dijkstra ́s algoritm [2] ochdubbelriktad sökning. Med flera rutter får användaren möjlighet attvälja den rutt som passar bäst utifrån personliga preferenser. Tillexempel antalet stopp längs med rutten eller tidsåtgång för rutten.Den resulterande metoden tar fram ett antal rutter som är under ettvillkor gällande maximal tillåten tidsåtgång.

Made available in DSpace on 2016-04-04T18:31:20Z (GMT). No. of bitstreams: 1 Alberto Lotito.pdf: 2153365 bytes, checksum: 3433c9bb5371bcce62f119c4593fe360 (MD5) Previous issue date: 2007-12-05 / This work intends to perform end-to-end traffic engineering through simulations in broadband multiprotocol networks and evaluate used parameters. We ve proposed and tested parameters used by the network administrator to dimension the action of an algorithm for Traffic Engineering. We dedicated special attention to IP networks interconnected to MPLS networks. Through simulations, we ve addressed questions of performance optimization, evaluating the network packet losses and compare the results with packet loss in the traditional OSPF network achieving improvements of up to 50%. This work contributes with improvements in traffic performance for real world networks, developing practical application since the traditional IP networks up to the present MPLS networks and also for mixed technologies. / Este trabalho tem como objetivos realizar simula??es de engenharia de tr?fego fim a fim em redes que trabalham com protocolos distintos e avaliar par?metros usados. Propusemos e testamos par?metros que servem para que o operador da rede dimensione a atua??o de um algoritmo para engenharia de tr?fego. Demos especial aten??o ?s redes que trabalham com IP interconectando-se a redes MPLS. Executando diversas simula??es, trabalhamos quest?es de melhoria de desempenho por meio de avalia??o da perda de pacotes nas redes testadas comparando-se os resultados com as tradicionais redes com protocolo OSPF e chegando a melhoria de at? 50% se comparado com este. Este trabalho contribui com melhorias em engenharia de tr?fego em redes do mundo real, desenvolvendo aplica??o pr?tica desde as tradicionais redes IP at? as atuais redes MPLS e tamb?m em redes de tecnologias mistas.

FundaÃÃo de Amparo à Pesquisa do Estado do Cearà / CoordenaÃÃo de AperfeiÃoamento de NÃvel Superior / Conselho Nacional de Desenvolvimento CientÃfico e TecnolÃgico / Neste trabalho propomos dois modelos para a geraÃÃo de fraturas em substratos regulares. No primeiro modelo, empregamos iterativamente o conceito de caminho crÃtico para determinar sistematicamente o elemento de menor âcondutividadeâ da rede. Estes elementos sÃo entÃo identificados como âfalhasâ e removidos permanentemente da estrutura atà que uma fratura macroscÃpica destrua a conectividade global da rede. Uma vez detectada, esta fratura à caracterizada topologicamente como uma estrutura auto-similar de dimensÃo fractal Dp ≈ 1.21. No segundo modelo, empregamos iterativamente o algoritmo de Dijkstra para determinar o caminho mÃnimo em uma paisagem aleatÃria, retirando sistematicamente desta estrutura o elemento de maior energia. Como no modelo anterior, estes elementos sÃo identificados como âfalhasâ atà que um conjunto conecto deles resulte em uma fratura macroscÃpica. A mÃdia realizada sobre vÃrias amostras de fraturas em diferentes tamanhos de substratos revela a presenÃa de uma estrutura auto-similar de dimensÃo fractal Df ≈ 1.21. A semelhanÃa numÃrica entre os expoentes Dp e Df sugere que os dois modelos pertencem à mesma classe de universalidade. / In this work we propose two models for fracture generation in regular substrates. In the first model, we iteratively apply the concept of critical path to systematically determine the lower âconductivityâ element in the connected spanning network. At each iteration, once these elements are identified as local âcracks ́ ́, they are permanently removed from the structure up to the point in which a macroscopic fracture can destroy the global network connectivity. This fracture is then topologically characterized as self-similar with fractal dimension Dp ≈ 1.21. In the second model, we employ the algorithm of Dijkstra to determine the minimal path in a random energy landscape and remove its highest energy element. As in the previous model, these elements are considered to be local âcracks ́ ́ till a subset of them can be identified as a macroscopic fracture. The average over many samples of fractures calculated for different system sizes reveals the presence of a self-similar structure with fractal dimension Df ≈ 1.21. The resemblance between the two exponents Dp e Df suggests that the two models belong to the same universality class.

<p>This thesis examines some of the best known algorithms for solving the shortest point-to-point path problem, and evaluates their performance on real metropolitan area networks. The focus has mainly been on Dijkstra‟s algorithm and different variations of it, and the algorithms have been implemented in C# for the practical tests. The size of the networks used in this study varied between 358 and 2464 nodes, and both running time and representative operation counts were measured.</p><p>The results show that many different factors besides the network size affect the running time of an algorithm, such as arc-to-node ratio, path length and network structure. The queue implementation of Dijkstra‟s algorithm showed the worst performance and suffered heavily when the problem size increased. Two techniques for increasing the performance were examined: optimizing the management of labelled nodes and reducing the search space. A bidirectional Dijkstra‟s algorithm using a binary heap to store temporarily labelled nodes combines both of these techniques, and it was the algorithm that performed best of all the tested algorithms in the practical tests.</p><p>This project was initiated by Netadmin Systems i Sverige AB who needed a new path finding module for their network management system NETadmin. While this study is primarily of interest for researchers dealing with path finding problems in computer networks, it may also be useful in evaluations of path finding algorithms for road networks since the two networks share some common characteristics.</p>