Dissertations / Theses on the topic 'Shortest paths'
To see the other types of publications on this topic, follow the link: Shortest paths.
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 50 dissertations / theses for your research on the topic 'Shortest paths.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.
1
Nagubadi, RadhaKrishna. "K Shortest Path Implementation." Thesis, Linköpings universitet, Databas och informationsteknik, 2013. http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-95451.
Full textAbstract:
The problem of computing K shortest loopless paths, or ranking of the K shortest loopless paths between a pair of given vertices in a network is a well-studied generalization of shortest path problem. The K shortest paths problem determines not only one shortest path but the K best shortest paths from s to t in an increasing order of weight of the paths. Yen’s algorithm is known to be the efficient and widely used algorithm for determining K shortest loopless paths. Here, we introduce a new algorithm by modifying the Yen’s algorithm in the following way: instead of removing the vertices and the edges from the graph, we store them in two different sets. Then we modified the Dijkstra’s algorithm by taking these two sets into consideration. Thus the algorithm applies glass box methodology by using the modified Dijkstra’s algorithm for our dedicated purpose. Thus the efficiency is improved. The computational results conducted over different datasets, shows the proposed algorithm has better performance results.
2
Shinn, Tong-Wook. "Combining Shortest Paths, Bottleneck Paths and Matrix Multiplication." Thesis, University of Canterbury. Computer Science and Software Engineering, 2014. http://hdl.handle.net/10092/9740.
Full textAbstract:
We provide a formal mathematical definition of the Shortest Paths for All Flows (SP-AF) problem and provide many efficient algorithms. The SP-AF problem combines the well known Shortest Paths (SP) and Bottleneck Paths (BP) problems, and can be solved by utilising matrix multiplication. Thus in our research of the SP-AF problem, we also make a series of contributions to the underlying topics of the SP problem, the BP problem, and matrix multiplication.
For the topic of matrix multiplication we show that on an n-by-n two dimensional (2D) square mesh array, two n-by-n matrices can be multiplied in exactly 1.5n ‒ 1 communication steps. This halves the number of communication steps required by the well known Cannon’s algorithm that runs
on the same sized mesh array.
We provide two contributions for the SP problem. Firstly, we enhance the breakthrough algorithm by Alon, Galil and Margalit (AGM), which was the first algorithm to achieve a deeply sub-cubic time bound for solving the All Pairs Shortest Paths (APSP) problem on dense directed graphs. Our enhancement allows the algorithm by AGM to remain sub-cubic for larger upper bounds on integer edge costs. Secondly, we show that for graphs with n vertices, the APSP problem can be solved in exactly 3n ‒ 2 communication steps on an n-by-n 2D square mesh array. This improves on the previous result of 3.5n communication steps achieved by Takaoka and Umehara.
For the BP problem, we show that we can compute the bottleneck of the entire graph without solving the All Pairs Bottleneck Paths (APBP) problem, resulting in a much more efficient time bound.
Finally we define an algebraic structure called the distance/flow semi-ring to formally introduce the SP-AF problem, and we provide many algorithms for solving the Single Source SP-AF (SSSP-AF) problem and the All Pairs SP-AF (APSP-AF) problem. For the APSP-AF problem, algebraic algorithms are given that utilise faster matrix multiplication over a ring.
3
Zhao, Hong Jun. "Towards online shortest paths computation." Thesis, University of Macau, 2011. http://umaclib3.umac.mo/record=b2550689.
Full text
4
Chénier, Christian. "Shortest paths in weighted polygons." Thesis, University of Ottawa (Canada), 1996. http://hdl.handle.net/10393/10034.
Full textAbstract:
Consider a polygon P and two points $p,\ q\in P.$ Suppose that to move from p to q, we can travel along the edges of P or through the interior of P. Assume that the speed at which we can travel along the edges of P is one unit per second, and the travel speed through the interior of P is 1/s units per seconds ($s>1$). The problem consists of finding the shortest path between p and q. We solve this problem in O(n) time for convex polygons. For simple polygons, we show two algorithms. The first algorithm runs in O(E log n) time using O(E) space (where E is the size of the visibility of P). The second algorithm has two variations which both require O(n E log n) preprocessing (where E is the number of edges in the visibility graph of P). The first variation takes O(n log n) query time and O($n\sp2$ log n) space. The second variation has a query time of O(n log$\sp2$ n) but uses $O(n\sp2)$ space. For the orthogonal case, we give a O(E) time and space algorithm.
5
Gao, Guo-Gang. "Planning shortest paths amongst discs." Thesis, McGill University, 1988. http://digitool.Library.McGill.CA:80/R/?func=dbin-jump-full&object_id=64080.
Full text
6
Moffat, Alistair. "Fast algorithms for shortest paths." Thesis, University of Canterbury. Computer Science, 1985. http://hdl.handle.net/10092/7926.
Full textAbstract:
The problem of finding all shortest paths in a non-negatively weighted directed graph is addressed, and a number of new algorithms for solving this problem on a graph of
n vertices and m edges are given. The first of these requires in the worst case min { 2mn, nᶟ } + O(n²˙⁵ ) addition and binary comparisons on path and edge costs, improving the previous bound (Dantzig, 1960) of n³ + O(n²logn) operations in a
computational model where addition and comparison are the only operations permitted on path costs.
The second algorithm presented, and the main result of this thesis, has an expected running time of O(n²logn) on graphs with edge weights drawn from an endpoint independent probability distribution, improving asymptotically the previous bound (Bloniarz, 1980) of O(n²lognlog*n), and resolving a major open problem (Bloniarz, 1983) concerning the complexity of the all pairs shortest path problem. Some variations on the new algorithm are analysed, and it is shown that two superficially good heuristics have a bad effect on the running time. A third variation reduces the worst case running time to O(nᶟ), making the method competitive with the O(nᶟ) classical algorithms of Dijkstra (1959) and Floyd (1962). The new algorithm is not just of theoretical interest - experimental results are given that show the algorithm to be fast for operational use, running an order of magnitude faster than the algorithms of Dijkstra and Floyd.
The closely linked problem of distance matrix multiplication is also investigated, and a number of fast average time distance matrix multiplication algorithms are given.
7
Chase, Melissa. "Shortest Path Problems: Multiple Paths in a Stochastic Graph." Scholarship @ Claremont, 2003. https://scholarship.claremont.edu/hmc_theses/143.
Full textAbstract:
Shortest path problems arise in a variety of applications ranging from transportation planning to network routing among others. One group of these problems involves finding shortest paths in graphs where the edge weights are defined by probability distributions. While some research has addressed the problem of finding a single shortest path, no research has been done on finding multiple paths in such graphs. This thesis addresses the problem of finding paths for multiple robots through a graph in which the edge weights represent the probability that each edge will fail. The objective is to find paths for n robots that maximize the probability that at least k of them will arrive at the destination. If we make certain restrictions on the edge weights and topology of the graph, this problem can be solved in O(n log n)time. If we restrict only the topology, we can find approximate solutions which are still guaranteed to be better than the single most reliable path.
8
Wang, I.-Lin. "Shortest paths and multicommodity network flows." Diss., Georgia Institute of Technology, 2003. http://hdl.handle.net/1853/23304.
Full text
9
Tabatabai, Bijan Oni. "An investigation of shortest paths algorithms." Thesis, Durham University, 1987. http://etheses.dur.ac.uk/6685/.
Full textAbstract:
In this work, we classify the shortest path problems, review all source algorithms and analyse the different implementations of single source algorithms using various list structures and labelling techniques. Furthermore, we study the Sensitivity Analysis of one-to-all problems and present an algorithm, Senet, for their Post Optimality Analysis. Senet determines all the critical values for the weight of an arc (which could be optimal, non-optimal or non-existant) at which the optimal solution changes. Senet also provides the updated optimal solution for every range formed by two successive critical values.
10
Garcia, Renan. "Resource constrained shortest paths and extensions." Diss., Atlanta, Ga. : Georgia Institute of Technology, 2009. http://hdl.handle.net/1853/28268.
Full textAbstract:
Thesis (M. S.)--Industrial and Systems Engineering, Georgia Institute of Technology, 2009.Committee Co-Chair: George L. Nemhauser; Committee Co-Chair: Shabbir Ahmed; Committee Member: Martin W. P. Savelsbergh; Committee Member: R. Gary Parker; Committee Member: Zonghao Gu.
11
Lorek, David Randolph. "Approximating shortest paths in large networks /." Electronic version (PDF), 2005. http://dl.uncw.edu/etd/2005/lorekd/davidlorek.pdf.
Full text
12
Cuerington, Andre M. "The shortest path problem in the plane with obstacles : bounds on path lengths and shortest paths within homotopy classes." Thesis, Monterey, California. Naval Postgraduate School, 1991. http://hdl.handle.net/10945/28532.
Full text
13
Li, Dan. "Shortest paths through a reinforced random walk." Thesis, Uppsala universitet, Analys och tillämpad matematik, 2011. http://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-153802.
Full text
14
Magnanti, Thomas L., and Prakash Mirchandani. "Shortest Paths, Network Design and Associated Polyhedra." Massachusetts Institute of Technology, Operations Research Center, 1990. http://hdl.handle.net/1721.1/5186.
Full textAbstract:
We study a specialized version of network design problems that arise in telecommunication, transportation and other industries. The problem, a generalization of the shortest path problem, is defined on an undirected network consisting of a set of arcs on which we can install (load), at a cost, a choice of up to three types of capacitated facilities. Our objective is to determine the configuration of facilities to load on each arc that will satisfy the demand of a single commodity at the lowest possible cost. Our results (i) demonstrate that the single-facility loading problem and certain "common breakeven point" versions of the two-facility and three-facility loading problems are polynomially solvable as a shortest path problem; (ii) show that versions of the twofacility loading problem are strongly NP-hard, but that a shortest path solution provides an asymptotically "good" heuristic; and (iii) characterize the optimal solution (that is, specify a linear programming formulation with integer solutions) of the common breakeven point versions of the two-facility and three-facility loading problems. In this development, we introduce two new families of facets, give geometric interpretations of our results, and demonstrate the usefulness of partitioning the space of the problem parameters to establish polyhedral integrality properties. Generalizations of our results apply to (i) multicommodity applications and (ii) situations with more than three facilities.
15
Persson, Nicklas. "Shortest paths and geodesics in metric spaces." Thesis, Umeå universitet, Institutionen för matematik och matematisk statistik, 2013. http://urn.kb.se/resolve?urn=urn:nbn:se:umu:diva-66732.
Full textAbstract:
This thesis is divided into three part, the first part concerns metric spaces and specically length spaces where the existence of shortest path between points is the main focus. In the second part, an example of a length space, the Riemannian geometry will be given. Here both a classical approach to Riemannian geometry will be given together with specic results when considered as a metric space. In the third part, the Finsler geometry will be examined both with a classical approach and trying to deal with it as a metric space.
16
Kholondyrev, Yury. "Optimistic and pessimistic shortest paths on uncertain terrains." Thesis, University of British Columbia, 2007. http://hdl.handle.net/2429/32577.
Full textAbstract:
In the Uncertain Terrain Shortest Path problem we consider a triangulated terrain with vertices having uncertain Z-coordinates: each vertex is denned as a (x,y,z―,z+) tuple, where the z coordinate of a vertex is uncertain and can be anywhere in the range from z― to z+. We are looking for a path (defined by its projection to the XY- plane) such that, over all possible terrains, the path is as short as possible. We look at both pessimistic (terrain arranges itself to maximize the length of the path that we choose) and optimistic (terrain takes the state that minimizes the length of our path) scenarios. We restrict ourselves to walk only along the edges of the terrain.
The unrestricted problem (when we are allowed to walk on the faces of the terrain) has been proven to be NP-hard in both pessimistic and optimistic scenarios. We prove that the edge-restricted pessimistic problem is NP-hard by providing a reduction from the SUBSET-SUM problem and give a polynomial time algorithm for the edge-restricted optimistic problem.Science, Faculty of
Computer Science, Department of
Graduate
17
Péchaud, Mickaël. "Shortest paths calculations, and applications to medical imaging." Phd thesis, Ecole Normale Supérieure de Paris - ENS Paris, 2009. http://tel.archives-ouvertes.fr/tel-00843997.
Full text
18
Pisaruk, Fabio. "K-menores caminhos." Universidade de São Paulo, 2009. http://www.teses.usp.br/teses/disponiveis/45/45134/tde-14072009-185725/.
Full textAbstract:
Tratamos da generalização do problema da geração de caminho mínimo, no qual não apenas um, mas vários caminhos de menores custos devem ser produzidos. O problema dos k-menores caminhos consiste em listar os k caminhos de menores custos conectando um par de vértices. Esta dissertação trata de algoritmos para geração de k-menores caminhos em grafos simétricos com custos não-negativos, bem como algumas implementações destes.We consider a long-studied generalization of the shortest path problem, in which not one but several short paths must be produced. The k-shortest (simple) paths problem is to list the k paths connecting a given source-destination pair in the digraph with minimum total length. This dissertation deals with k-shortest simple paths algorithms designed for nonnegative costs, undirected graphs and some implementations of them.
19
Tian, Lin. "Improved Shortest Path Algorithms by Dynamic Graph Decomposition." Thesis, University of Canterbury. Computer Science and Software Engineering, 2006. http://hdl.handle.net/10092/1196.
Full textAbstract:
In this thesis, we introduce three new approaches for solving the single source shortest path (SSSP) problem in nearly acyclic directed graphs, and algorithms based on these approaches. In the first approach, we extend a technique of strongly connected components (sc-components) decomposition by Takaoka [23], and the generalized decomposition approach is called a higher-order decomposition. According to Takaoka's definition of acyclicity, the degree of cyclicity of a graph G, cyc(G), is defined by the maximum cardinality of the strongly connected components of G. Based on the higher-order decomposition, we give a generalization of Takaoka's definition of acyclicity. That is, the degree of cyclicity cych(G) is the maximum cardinality of the hth order strongly connected components of G, where h is the number of times that the graph has been decomposed. Then, the original definition introduced by Takaoka [23] can be presented as: The degree of cyclicity cyc(G) is the maximum cardinality of the 1th order strongly connected components of G. The second approach presents a new method for measuring acyclicity based on modifications to two existing methods. In the new method, we decompose the given graph into a 1-dominator set, which is a set of acyclic subgraphs, where each sub-graph is dominated by one trigger vertex. Meanwhile we compute sc-components of a degenerated graph derived from triggers. Using this preprocessing, we can efficiently compute the single source shortest paths (SSSPs) for nearly acyclic graphs in O(m + r logl ) time, where r is the size of the 1-dominator set, and l is the size of the largest sc-component. In the third approach, we modify the concept of a 1-dominator set to that of a 1-2-dominator set, and achieve O(m + r²) time to compute a 1- 2-dominator set in a graph. Each of acyclic sub-graphs obtained by the 1-2-dominator set are dominated by one or two trigger vertices cooperatively. Such sub-graphs are potentially larger than those decomposed by the 1-dominator set. Thus fewer trigger vertices are needed to cover the graph, that is, rʹ ≤ r, where rʹ is the number of triggers in the 1-2-dominator set. When rʹ is much smaller than r, we can efficiently compute SSSPs in O(m + rʹlogrʹ) time.
20
Rossolini, Andrea. "Analysis and Implementation of Algorithms for Bicriteria Shortest Paths Problems." Bachelor's thesis, Alma Mater Studiorum - Università di Bologna, 2019. http://amslaurea.unibo.it/19617/.
Full textAbstract:
Questa tesi si pone l'obbiettivo di affrontare ed analizzare un problema di pathfinding partendo da un'analisi di alcuni algoritmi per la ricerca del percorso più breve su normali grafi, per poi ampliare lo studio e concentrarsi su algoritmi che calcolano molteplici percorsi su grafi che utilizzano due pesi per ogni arco. Gli algoritmi per i grafi `bicriteria' (appunto che considerano due pesi su ogni arco) verranno analizzati, implementati e le loro soluzioni confrontate con gli altri algoritmi, al fine di individuare i più efficienti in termini di tempo di elaborazione e quelli che riescono a minimizzare al meglio i pesi degli archi dei cammini trovati, quindi valutando quantità e qualità delle soluzioni.
Dato che, lo studio di algoritmi per la ricerca del percorso più breve in grafi classici è piuttosto celebre in letteratura, è ormai facile trovare implementazioni che permettano di risolvere questo problema. Verrà effettuata quindi una rapida implementazione ed analisi riguardante gli algoritmi `monocriteria'. Per agli algoritmi che lavorano in grafi con più pesi, per i quali è più difficile reperire implementazioni ed analisi, ci sarà una spiegazione più approfondita ed accurata, soffermandosi anche su casi particolari e indicando le scelte implementative fatte per ottimizzare al meglio le loro prestazioni. L'analisi dei risultati confronterà, come già detto, l'insieme delle soluzioni calcolate dai vari algoritmi ed i loro tempi di elaborazione. Inoltre i suddetti algoritmi verranno utilizzati su mappe di alcune città, prese come esempio, per poter fare un confronto visivo sui cammini minimi trovati ed i nodi visitati durante l'elaborazione degli algoritmi; in modo da semplificare e rendere più immediato il confronto tra le varie implementazioni.
21
Crane, Jerry Allen. "Searching for Shortest and Safest Paths Along Obstacle Common Tangents." Thesis, Monterey, California. Naval Postgraduate School, 1991. http://hdl.handle.net/10945/43782.
Full textAbstract:
This thesis describes a method for computing globally shortest paths for a point robot in a two-dimensional, orthogonal world composed of convex and concave polygons through the construction of obstacle common tangent visibility graphs. Visibility and intersection testing are based on the orientation of three or more points in the plane, and complex obstacle tangent visibility graphs are constructed using only these orientation relationships. Obstacle common tangents for convex and concave polygonal obstacles are implemented as a computational representation of locally shortest paths. A series of tangent sequences form global paths which equate to global path equivalence classes, effectively reducing the path finding problem to that of finding the shortest path in the path equivalence class. A simple and logical approach for processing concave polygons using convex subpolygons is implemented, allowing common tangent construction and path searching algorithms to process complex geometrical shapes in an efficient and symbolically unique fashion. Dijkstra's algorithm is implemented using heuristic control for optimal path searching. The framework for utilizing constant clearance strips for safe path planning along obstacle common tangents is presented but not fully implemented.
22
Wagner, Mitchell James. "Reconstructing Signaling Pathways Using Regular-Language Constrained Paths." Thesis, Virginia Tech, 2018. http://hdl.handle.net/10919/85044.
Full textAbstract:
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
23
Chen, Lijuan. "An efficient method to compute shortest paths in real road network /." View abstract or full-text, 2005. http://library.ust.hk/cgi/db/thesis.pl?IEEM%202005%20CHEN.
Full text
24
Nannicini, Giacomo. "Point-to-point shortest paths on dynamic time-dependent road networks." Phd thesis, Ecole Polytechnique X, 2009. http://pastel.archives-ouvertes.fr/pastel-00005275.
Full text
25
Turner, Lara Ruth [Verfasser]. "Universal Combinatorial Optimization: Matroid Bases and Shortest Paths / Lara Ruth Turner." München : Verlag Dr. Hut, 2013. http://d-nb.info/1033041297/34.
Full text
26
Bonaventura, Moreno. "Shortest paths to success : network indicators of performance in innovation ecosystems." Thesis, Queen Mary, University of London, 2017. http://qmro.qmul.ac.uk/xmlui/handle/123456789/24555.
Full textAbstract:
In this thesis I show how various theories and methodologies borrowed from complexity science, organisation science, and network science can be suitably integrated to provide a comprehensive and interdisciplinary approach to the study of innovation processes. I study the network foundations of success in innovation ecosystems and I conduct several empirical investigations to identify those network characteristics that are expected to correlate with positive outcomes and success. I assess the extent to which the diversity and the strength in the networks of relationships boost the performance and success of scientists and early-stage firms. To this end I analyse two large-scale data sets about scientific publishing and start-up firms by making use of already existing topological network measures and by proposing novel measures to characterise the degree of interdisciplinarity and access to diverse pools of knowledge in scientific collaborations. Results provide empirical support to the idea that collaboration sustains innovation and performance by facilitating knowledge diffusion, acquisition and creation. First, results indicate that the networks of interaction between start-ups have a strong impact on the firms' longterm success. Second I find that, while abandoning specialisation in favour of moderate degrees of interdisciplinarity deteriorates scientific performance, very interdisciplinary scientists tend to outperform specialised ones. Additionally, I address the computational challenges related to the size of the data sets used and their time-varying nature. In particular I focus on the scalability challenges of incremental graph algorithms. The thesis contributes in this direction by proposing new efficient algorithms and data structures to handle and to analyse large graphs whose nodes and edges change rapidly over time. These efforts have been collected and made available to the public in the form of a web platform (http://lab.startup-network.org/) and an open-source python package, NetworkL (https://networkl.github.io/).
27
Wrede, Simon. "Memory efficient Monte Carlo methods for computing shortest paths in stochastic graphs." Thesis, Linköpings universitet, Programvara och system, 2021. http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-178160.
Full textAbstract:
Threat modeling for information technology infrastructure can be done using shortest path algorithms in stochastic graphs. By modeling the infrastructure as a graph, potential vulnerabilities may be presented by computing what paths an attacker might take. This thesis project presents and compares two memory efficient algorithms that can be used to solve this problem approximately, the online k-means and sampled k-shortest path algorithm. By computing paths for several different graph types, the two algorithms were compared against a naive algorithm. The online k-means algorithm uses approximately 77 times less memory, executes in the same amount of time, and produces similar path lengths. In our experiments, the sampled k-shortest path algorithm uses approximately 154 times less memory, execution time is seen to be lowered by a factor of 5 to 20 depending on the graph type, but path distances computed are longer.
28
Subramanian, Shivaram. "Routing Algorithms for Dynamic, Intelligent Transportation Networks." Thesis, Virginia Tech, 1997. http://hdl.handle.net/10919/37056.
Full textAbstract:
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
29
Ganugpati, Sridevi V. 1975. "Dynamic shortest paths algorithms : parallel implementations and application to the solution of dynamic traffic assignment models." Thesis, Massachusetts Institute of Technology, 1998. http://hdl.handle.net/1721.1/46478.
Full text
30
Vladu, Adrian Valentin. "Shortest paths, Markov chains, matrix scaling and beyond : improved algorithms through the lens of continuous optimization." Thesis, Massachusetts Institute of Technology, 2017. http://hdl.handle.net/1721.1/112828.
Full textAbstract:
Thesis: Ph. D., Massachusetts Institute of Technology, Department of Mathematics, 2017.This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections.
Cataloged from student-submitted PDF version of thesis.
Includes bibliographical references (pages 289-302).
In this thesis, we build connections between classic methods from convex optimization and the modern toolkit from the fast Laplacian solver literature, in order to make progress on a number of fundamental algorithmic problems: *-- We develop a faster algorithm for the unit capacity minimum cost flow problem, which encompasses the shortest path with negative weights and minimum cost bipartite perfect matching problems. In the case of sparse graphs, this provides the first running time improvement for these problems in over 25 years. *-- We initiate the study of solving linear systems involving directed Laplacian matrices, and devise an almost-linear time algorithm for this task. This primitive enables us to also obtain almost-linear time algorithms for computing an entire host of quantities associated with Markov chains, such as stationary distributions, personalized PageRank vectors, hitting times, or escape probabilities. This significantly improves over the previous state-of-the-art, which was based on simulating random walks, or applying fast matrix multiplication. *-- We develop faster algorithms for scaling and balancing nonnegative matrices, two fundamental problems in scientific computing, significantly improving over the previously known best running times. In particular, if the optimal scalings/balancings have polynomially bounded condition numbers, our algorithms run in nearly-linear time. Beyond that, we leverage and extend tools from convex geometry in order to design an algorithm for online pricing with nearly-optimal regret. We also use convex optimization to shed a new light on the approximate Caratheodory problem, for which we give a deterministic nearly-linear time algorithm, as well as matching lower bounds.
by Adrian Valentin Vladu.
Ph. D.
31
Kykuta, Diogo Haruki. "Comparação de algoritmos para o Problema dos K Menores Caminhos." Universidade de São Paulo, 2018. http://www.teses.usp.br/teses/disponiveis/45/45134/tde-20032018-003225/.
Full textAbstract:
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.
32
Çaylak, Kayaturan Gökçe. "Representing shortest paths in graphs using Bloom filters without false positives and applications to routing in computer networks." Thesis, University of Essex, 2018. http://repository.essex.ac.uk/22334/.
Full textAbstract:
A Bloom filter is data structure for representing sets in a compressed form, which has many applications. Bloom filters save time and space, but produce errors known as false positives. In this thesis, a new approach is suggested. Instead of choosing labels for edges in graphs at random (as is done in the standard Bloom filter approach), labels for edges are chosen based on the graph and the position of an edge in the graph. It is shown that under some assumptions (the graph is known, and only shortest paths are encoded), there will be no false positives leading to a message being delivered to a wrong node.
33
Muhandiramge, Ranga. "Maritime manoeuvring optimization : path planning in minefield threat environments." University of Western Australia. School of Mathematics and Statistics, 2008. http://theses.library.uwa.edu.au/adt-WU2009.0015.
Full textAbstract:
The aim of the research project that is the subject of this thesis is to apply mathematical techniques, especially those in the area of operations research, to the problem of maritime minefield transit. We develop several minefield models applicable to different aspects of the minefield problem. These include optimal mine clearance, shortest time traversal and time constrained traversal. We hope the suite of models and tools developed will help make mine field clearance and traversal both safer and more efficient and that exposition of the models will bring a clearer understanding of the mine problem from a mathematical perspective. In developing the solutions to mine field models, extensive use is made of network path planning algorithms, particularly the Weight Constrained Shortest Path Problem (WCSPP) for which the current state-of-the-art algorithm is extended. This is done by closer integration of Lagrangean relaxation and preprocessing to reduce the size of the network. This is then integrated with gap-closing algorithms based on enumeration to provide optimal or near optimal solutions to the path planning problem. We provide extensive computational evidence on the performance of our algorithm and compare it to other algorithms found in the literature. This tool then became fundamental in solving various separate minefield models. Our models can be broadly separated into obstacle models in which mine affected regions are treated as obstacles to be avoided and continuous threat in which each point of space has an associated risk. In the later case, we wish to find a path that minimizes the integral of the risk along the path while constraining the length of the path. We call this the Continuous Euclidean Length Constrained Minimum Cost Path Problem (C-LCMCPP), for which we present a novel network approach to solving this continuous problem. This approach results in being able to calculate a global lower bound on a non-convex optimization problem.
34
Suryasaputra, Robert, and rsuryasaputra@gmail com. "Congestion Removal in the Next Generation Internet." RMIT University. Electrical and Computer Engineering, 2007. http://adt.lib.rmit.edu.au/adt/public/adt-VIT20080521.114723.
Full textAbstract:
The ongoing development of new and demanding Internet applications requires the Internet to deliver better service levels that are significantly better than the best effort service that the Internet currently provides and was built for. These improved service levels include guaranteed delays, jitter and bandwidth. Through extensive research into Quality of Service and Differentiated Service (DiffServ) it has become possible to provide guaranteed services, however this turns out to be inadequate without the application of Traffic Engineering methodologies and principles. Traffic Engineering is an integral part of network operation. Its major goal is to deliver the best performance from an existing service provider's network resources and, at the same time, to enhance a customers' view of network performance. In this thesis, several different traffic engineering methods for optimising the operation of native IP and IP networks employing MPLS are proposed. A feature of these new methods is their fast run times and this opens the way to making them suitable for application in an online traffic engineering environment. For native IP networks running shortest path based routing protocols, we show that an LP-based optimisation based on the well known multi-commodity flow problem can be effective in removing network congestion. Having realised that Internet service providers are now moving towards migrating their networks to the use of MPLS, we have also formulated optimisation methods to traffic engineer MPLS networks by selecting suitable routing paths and utilising the feature of explicit routing contained in MPLS. Although MPLS is capable of delivering traffic engineering across different classes of traffic, network operators still prefer to rely on the proven and simple IP based routing protocols for best effort traffic and only use MPLS to route traffic requiring special forwarding treatment. Based on this fact, we propose a method that optimises the routing patterns applicable to different classes of traffic based on their bandwidth requirements. A traffic engineering comparison study that evaluates the performance of a neural network-based method for MPLS networks and LP-based weight setting approach for shortest path based networks has been performed using a well-known open source network simulator, called ns2. The comparative evaluation is based upon the packet loss probability. The final chapter of the thesis describes the software development of a network management application called OptiFlow which integrates techniques described in earlier chapters including the LP-based weight setting optimisation methodology; it also uses traffic matrix estimation techniques that are required as input to the weight setting models that have been devised. The motivation for developing OptiFlow was to provide a prototype set of tools that meet the congestion management needs of networking industries (ISPs and telecommunications companies - telcos).
35
Souza, Marcelo de. "Um método biobjetivo de alocação de tráfego para veículos convencionais e elétricos." reponame:Biblioteca Digital de Teses e Dissertações da UFRGS, 2015. http://hdl.handle.net/10183/130509.
Full textAbstract:
A busca de soluções para a mobilidade urbana que minimizem a agressão do setor de tráfego e transportes ao meio ambiente está cada vez maior. Os veículos elétricos se posicionam como uma alternativa interessante, pois reduzem a emissão de gases poluentes na atmosfera, a poluição sonora e o consumo de petróleo. No entanto, sua limitada autonomia e a escassez de postos de recarga intimidam sua adoção. Por conta disso, políticas governamentais de incentivo têm sido desenvolvidas para a oferta de benefícios a quem optar por um veículo elétrico. Estima-se que dentro de poucas décadas toda a frota urbana será substituída por veículos dessa natureza. Por isso, é importante entender as mudanças no tempo de viagem e no consumo de energia oriundos da inclusão de veículos elétricos em cenários de tráfego. Trabalhos anteriores estudaram as diferenças entre os mecanismos internos de veículos convencionais e elétricos na determinação destas mudanças. Porém, dadas as características destes últimos, motoristas de veículos elétricos se preocupam com a economia de energia e podem optar por rotas diferentes. Logo, uma análise completa destes impactos deve considerar uma nova distribuição de tráfego. Este trabalho propõe um método biobjetivo de alocação de tráfego que considera o tempo de viagem e o consumo de energia para determinar a distribuição de veículos elétricos em cenários de tráfego urbano. Duas estratégias de distribuição de fluxo são propostas como mecanismos de escolha de rotas. Como parte da alocação de tráfego, é proposto um algoritmo biobjetivo de caminhos mínimos para veículos elétricos. A abordagem apresentada foi aplicada a três cenários distintos, onde percebeu-se uma diminuição de até 80% no consumo total de energia. Em cenários com congestionamento, observou-se um aumento de 10% no tempo de viagem. Já em cenários sem congestionamento o tempo de viagem diminuiu cerca de 2%. A recuperação de energia representa quase 6% da economia total dos veículos elétricos. Além disso, experimentos mostraram que investimentos na eficiência dos veículos elétricos podem resultar em uma economia de até 15% de energia.The search for urban mobility solutions that minimize the aggression to the environment is increasing. Electric vehicles are an attractive alternative because they reduce greenhouse gas emissions, noise pollution, and oil consumption. However, their limited autonomy and the lack of charging stations restrict their popularization. Therefore, government incentive policies have been developed in order to offer benefits to those who choose an electric vehicle. It is estimated that the entire urban fleet will be replaced by these vehicles in a few decades. Therefore, it is important to understand the changes in travel time and energy consumption from the inclusion of electric vehicles in traffic scenarios. Previous works determined these changes by studying the differences between the internal engine of conventional and electric vehicles. However, given the characteristics of the latter, drivers of electric vehicles care about saving energy and may want to choose different routes. Thus, a complete analysis of these impacts should consider a redistribution of traffic. This work proposes a bi-objective traffic assignment method that considers the travel time and the energy consumption to determine the distribution of electric vehicles in urban traffic scenarios. We introduce two strategies for flow distribution as models of route choice. As a procedure of the traffic assignment method, we propose a bi-objective shortest path algorithm for electric vehicles. Our approach was applied to three different scenarios, which resulted in a decrease of up to 80% in total energy consumption. In congested scenarios, we observe an increase of about 10% in average travel time. In uncongested scenarios, travel time decreases about 2%. Energy recovery is almost 6% of the total savings of electric vehicles. Moreover, experiments have shown that investments in the efficiency of electric vehicles can result in up to 15% of energy savings.
36
Krauter, Michal. "Nejkratší cesty v grafu." Master's thesis, Vysoké učení technické v Brně. Fakulta informačních technologií, 2009. http://www.nusl.cz/ntk/nusl-236740.
Full textAbstract:
This thesis deals with shortest paths problem in graphs. Shortest paths problem is the basic issue of graph theory with many pracitcal applications. We can divide this problem into two following generalizations: single-source shortest path problem and all-pairs shortest paths problem. This text introduces principles and algorithms for generalizations. We describe both classical and new more efficient methods. It contains information about how some of these algorithms were implemented and offers an experimental comparison of these algorithms.
37
Gueye, Fallou. "Algorithmes de recherche d'itinéraires en transport multimodal." Thesis, Toulouse, INSA, 2010. http://www.theses.fr/2010ISAT0042.
Full textAbstract:
Ce travail de thèse s’est intéressé au transport urbain de passagers dans un contexte d’offre de transport multimodale consistant en la coexistence de plusieurs modes de transport. Dans la pratique, un problème de transport multimodal nécessite la prise en compte de plusieurs objectifs et de contraintes spécifiques liées aux modes ou à la séquence de modes utilisés. De telles contraintes sont appelées contraintes de viabilité.Cette thèse CIFRE s’est déroulée en collaboration avec la société MobiGIS, spécialisée dans le conseil et le développement d’applications autour des Systèmes d’Information Géographiques.Le problème étudié dans cette thèse est celui de la recherche d’itinéraires viables multimodaux point à point bi-objectif pour lequel il s’agit à la fois de minimiser le temps de trajet et le nombre de changements de mode. Compte tenu notamment des objectifs considérés, ce problème est de complexité polynomiale.Sur la base d’une modélisation multi-couches des réseaux de transport multimodaux et d’une modélisation par un automate à états finis des contraintes de viabilité nous avons proposé différents algorithmes de résolution de ce problème basés sur le principe de fixation et extension de labels. Nous avons également proposé une règle de dominance basée sur les états de l’automate de viabilité et permettant d’élaguer le nombre de labels explorés par nos algorithmes. Des adaptations en bidirectionnel ou en utilisant le principe de la recherche A_ ont également été proposées.Les algorithmes proposés ont été évalués sur une partie du réseau de transport de la ville de Toulouse et les expérimentations ont mis en évidence l’intérêt de la règle de dominance basée sur les états ainsi que de l’approche bidirectionnelle développée.Un prototype logiciel implémentant différentes fonctionnalités des algorithmes de plus courts chemins a été développé. Il permet notamment de réaliser des calculs d’itinéraires point à point, des calculs d’accessibilité ou des calculs de distancierThis thesis focuses on urban passenger multimodal transportation. In practice, a multimodal transportation problem requires taking into account several objectives and specific constraints related to modes or sequence of used modes. Such constraints are called viability constraints. This work has been carried out in collaboration with MobiGIS, a company specialized in consulting and development of applications around Geographical Information Systems.The problem studied in this thesis is the bi-objective multimodal viable point-to-point shortest path, aiming at minimizing the total travel time and the total number of mode changes. Given the considered objectives, this problem is polynomial.On the basis of a multi-layered graph model of the multimodal transportation networks, and of a finite state automaton model of the viability constraints, we propose various algorithms for solving this problem, based on the principle of label setting and extension.We also proposed a new dominance rule based on the states of the automaton to reduce the number of labels explored by our algorithms. Bidirectional and A* variants are also proposed.The algorithms are evaluated the transportation network of the city of Toulouse and experiments demonstrate the interest of the proposed dominance rules and bidirectional approach. A prototype software implementing different features of the shortest path algorithms has been developed. It notably enables calculations of point-to-point routes, accessibility and origin-destination matrices
38
Iglesias, Alexandre. "Calcul d'itinéraire multicritère en transport multimodal." Thesis, Lyon, 2017. http://www.theses.fr/2017LYSEM025/document.
Full textAbstract:
Les travaux effectués dans cette thèse industrielle concernent l'amélioration du calculateur d'itinéraire de Cityway, société spécialisée dans les technologies de l’information appliquées à la mobilité.Nous avons d'abord établi un état de l'art exhaustif, accompagné d'une mise en perspective de l'existant Cityway avec celui-ci. Cela nous a permis d'aider l'entreprise à prendre du recul sur son produit et de justifier les axes de recherche choisis pour nos travaux.Nous nous sommes ensuite intéressés à l'aspect multicritère du problème. En effet, le calculateur, basé sur l'algorithme de Dijkstra, permet de trouver des trajets minimisant une somme pondérée de critères. Nous avons développé un algorithme multilabel permettant de conserver et étendre plusieurs labels au même nœud. Malgré une légère augmentation des temps de calculs, des résultats satisfaisants ont été obtenus dans une application bicritère de ce nouvel algorithme.Nous avons également travaillé sur la génération et la sélection de trajets alternatifs. La génération s'appuie sur les algorithmes monolabel ou multilabel. La sélection s'appuie quant à elle sur la définition d'une distance entre les solutions et des méthodes de regroupement.Enfin, nous nous sommes intéressés à l'optimisation du calcul du critère lexicographique de durée minimale dans le cas bicritère. Pour qu'un trajet soit intéressant, il faut qu'il soit optimal sur les critères usuels, mais aussi qu'il dure le moins longtemps possible. L'utilisation de certaines propriétés sur ce critère permet de réduire des temps de calcul initialement trop longsThe work carried out in this industrial PhD aims at improving the route planner of Cityway, a company specialized in information technologies applied to mobility. We first established an exhaustive state of the art, and compared it to the existing Cityway product. This allowed us to help the company take a step back from its urgent needs, and justify the research guidelines chosen for our work.We then looked at the multi-criteria aspect of the problem. Indeed, the trip planner, based on the Dijkstra algorithm, makes it possible to find paths minimizing a weighted sum of criteria. We have developed a multilabel algorithm to maintain and extend multiple labels at the same node. Despite a slight increase in computation time, satisfactory results were obtained in a bicriteria application of this new algorithm.We also worked on the generation and selection of alternative routes. The generation algorithm relies on the existing monolabel or newly developed multilabel algorithms. The selection algorithm is based on the definition of a distance between trips and adaptations of existing clustering algorithms to this specific case.Finally, we were interested in what we called the lexicographic criterion. For a trip to be interesting, it must be optimal on the usual criterion of earliest arrival, and, for trips arriving at the same time, on the latest departure criterion. The use of certain properties on this criterion makes it possible to reduce computation times on the bicriteria case
39
Diot, Emilie. "Etude structurelle et algorithmique des graphes pouvant être séparés avec des plus courts chemins." Thesis, Bordeaux 1, 2011. http://www.theses.fr/2011BOR14425/document.
Full textAbstract:
Les graphes sont des objets couramment utilisés pour modéliser de nombreuses situations réelles comme des réseaux routiers, informatiques ou encore électriques. Ils permettent de résoudre des problèmes sur ces réseaux comme le routage (aller d'un sommet à un autre en suivant les arêtes du graphe) ou encore leur exploration (obtenir une carte du graphe étudié). Les réseaux étudiés, et donc les graphes qui les modélisent, peuvent être grands, c'est-à-dire avoir un très grand nombre de sommets. Dans ce cas, comme dans le cas de l'étude de grandes données en général, nous pouvons utiliser le paradigme << Diviser pour mieux régner >> pour répondre aux questions posées. En effet, en travaillant sur des petites parties du graphe et en fusionnant les résultats obtenus sur ces petites parties, on peut obtenir le résultat sur le graphe global. Dans ce document, nous présenterons une manière de décomposer les graphes en utilisant des plus courts chemins comme séparateurs. Cette décomposition permet d'obtenir, par exemple, un routage efficace, un étiquetage compacte pour pouvoir estimer les distances entre les sommets d'un graphe ou encore une navigation efficace dans les graphes<< petit monde >>. Cette méthode va nous permettre de définir de nouvelles classes de graphesGraphs are widely used to MODELISER a lot of real situations like road networks, computers networks or electricity ones. Using them, we can solve problems on these networks like routing (go from a vertex ti another one) or explore them (to have a map of studied graph).Studied networks, and so graphs which MODELISER them, can be large (i.e. have a lot of vertices). In this case, we can use the paradigm "Divide and conquer" to answer the questions. Indeed, working on small parts of graphs and merging the results on these small parts, we can obtain the result on the whole graph.In this document, we present a way to separate graphs using shortest paths like separators. This decomposition let to obtain a compact routing, a compact labeling to estimate the distance between vertices of the graph. This method let us to define new class of graphs
40
Delhome, Raphaël. "Modélisation de la variabilité des temps de parcours et son intégration dans des algorithmes de recherche du plus court chemin stochastique." Thesis, Lyon, 2016. http://www.theses.fr/2016LYSET010/document.
Full textAbstract:
La représentation des temps de parcours est un enjeu influençant la qualité de l’information transmise aux usagers des réseaux de transport. En particulier, la congestion constitue un inconvénient majeur dont la prise en compte n’est pas toujours maîtrisée au sein des calculateurs d’itinéraires. De même, les évènements comme les réductions de capacité, les perturbations climatiques, ou encore les pics de fréquentation incitent à dépasser la définition statique des temps de parcours. Des travaux antérieurs se sont focalisés sur des temps dynamiques, i.e. dépendants de la date de départ, de manière à affiner le détail de la représentation, et à prendre notamment en compte le caractère périodique des congestions. La considération d’informations en temps réel est aussi une amélioration indéniable, que ce soit lors de la préparation du trajet, ou lorsqu’il s’agit de s’adapter à des perturbations rencontrées en cours de route. Ceci dit, aussi fines qu’elles soient dans les calculateurs disponibles, ces modélisations présentent un inconvénient majeur : elles ne prennent pas en compte toutes les facettes de la variabilité des temps de parcours. Cette variabilité est très importante, en particulier si l’on considère le niveau d’aversion au risque des usagers. En outre, dans un réseau multimodal, les correspondances éventuelles rendent encore plus critique l’incertitude associée aux temps de parcours. En réponse à ces enjeux, les présents travaux de thèse ont ainsi été consacrés à l’étude de temps de parcours stochastiques, i.e. vus comme des variables aléatoires distribuées.Dans une première étape, nous nous intéressons à la modélisation statistique des temps de parcours et à la quantification de leur variabilité. Nous proposons l’utilisation d’un système de lois développé dans le domaine de l’hydrologie, la famille des lois de Halphen. Ces lois présentent les caractéristiques typiques des distributions de temps de parcours, elles vérifient par ailleurs la propriété de fermeture par l’addition sous certaines hypothèses afférentes à leurs paramètres. En exploitant les ratios de moments associés aux définitions de ces lois de probabilité, nous mettons également au point de nouveaux indicateurs de fiabilité, que nous confrontons avec la palette d’indicateurs classiquement utilisés. Cette approche holistique de la variabilité des temps de parcours nous semble ainsi ouvrir de nouvelles perspectives quant au niveau de détail de l’information, notamment à destination des gestionnaires de réseaux.Par la suite, nous étendons le cadre d’analyse aux réseaux, en utilisant les résultats obtenus à l’étape précédente. Différentes lois de probabilité sont ainsi testées dans le cadre de la recherche du plus court chemin stochastique. Cette première étude nous permet de dresser un panorama des chemins identifiés en fonction du choix de modélisation. S’il est montré que le choix du modèle est important, il s’agit surtout d’affirmer que le cadre stochastique est pertinent. Ensuite, nous soulevons la relative inefficacité des algorithmes de recherche du plus court chemin stochastique, ceux-ci nécessitant des temps de calcul incompatibles avec un passage à l’échelle industrielle. Pour pallier cette difficulté, un nouvel algorithme mettant en oeuvre une technique d’accélération tirée du cadre déterministe est développé dans la dernière partie de la thèse. Les résultats obtenus soulignent la pertinence de l’intégration de modèles stochastiques au sein des calculateurs d’itinérairesThe travel time representation has a major impact on user-oriented routing information. In particular, congestion detection is not perfect in current route planners. Moreover, the travel times cannot be considered as static because of events such as capacity drops, weather disturbances, or demand peaks. Former researches focused on dynamic travel times, i.e. that depend on departure times, in order to improve the representation details, for example concerning the periodicity of congestions. Real-time information is also a significant improvement for users aiming to prepare their travel or aiming to react to on-line events. However these kinds of model still have an important drawback : they do not take into account all the aspects of travel time variability. This dimension is of huge importance, in particular if the user risk aversion is considered. Additionally in a multimodal network, the eventual connections make the travel time uncertainty critical. In this way the current PhD thesis has been dedicated to the study of stochastic travel times, seen as distributed random variables.In a first step, we are interested in the travel time statistical modeling as well as in the travel time variability. In this goal, we propose to use the Halphen family, a probability law system previously developed in hydrology. The Halphen laws show the typical characteristics of travel time distributions, plus they are closed under addition under some parameter hypothesis. By using the distribution moment ratios, we design innovative reliability indexes, that we compare with classical metrics. This holistic approach appears to us as a promising way to produce travel time information, especially for infrastructure managers.Then we extend the analysis to transportation networks, by considering previous results. A set of probability laws is tested during the resolution of the stochastic shortest path problem. This research effort helps us to describe paths according to the different statistical models. We show that the model choice has an impact on the identified paths, and above all, that the stochastic framework is crucial. Furthermore we highlight the inefficiency of algorithms designed for the stochastic shortest path problem. They need long computation times and are consequently incompatible with industrial applications. An accelerated algorithm based on a deterministic state-of-the-art is provided to overcome this problem in the last part of this document. The obtained results let us think that route planners might include travel time stochastic models in a near future
41
Murekatete, Rachel Mundeli. "An Analysis of Consequences of Land Evaluation and Path Optimization." Licentiate thesis, KTH, Geoinformatik, 2018. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-235687.
Full textAbstract:
Planners who are involved in locational decision making often use raster-based geographic information systems (GIS) to quantify the value of land in terms of suitability or cost for a certain use. From a computational point of view, this process can be seen as a transformation of one or more sets of values associated with a grid of cells into another set of such values through a function reflecting one or more criteria. While it is generally anticipated that different transformations lead to different ‘best’ locations, little has been known on how such differences arise (or do not arise). Examples of such spatial decision problems can be easily found in the literature and many of them concern the selection of a set of cells (to which the land use under consideration is allocated) from a raster surface of suitability or cost depending on context. To facilitate GIS’s algorithmic approach, it is often assumed that the quality of the set of cells can be evaluated as a whole by the sum of their cell values. The validity of this assumption must be questioned, however, if those values are measured on a scale that does not permit arithmetic operations. Ordinal scale of measurement in Stevens’s typology is one such example. A question naturally arises: is there a more mathematically sound and consistent approach to evaluating the quality of a path when the quality of each cell of the given grid is measured on an ordinal scale? The thesis attempts to answer the questions highlighted above in the context of path planning through a series of computational experiments using a number of random landscape grids with a variety of spatial and non-spatial structures. In the first set of experiments, we generated least-cost paths on a number of cost grids transformed from the landscape grids using a variety of transformation parameters and analyzed the locations and (weighted) lengths of those paths. Results show that the same pair of terminal cells may well be connected by different least-cost paths on different cost grids though derived from the same landscape grid and that the variation among those paths is affected by how given values are distributed in the landscape grid as well as by how derived values are distributed in the cost grids. Most significantly, the variation tends to be smaller when the landscape grid contains more distinct patches of cells potentially attracting or distracting cost-saving passage or when the cost grid contains a smaller number of low-cost cells. The second set of experiments aims to compare two optimization models, minisum and minimax (or maximin) path models, which aggregate the values of the cells associated with a path using the sum function and the maximum (or minimum) function, respectively. Results suggest that the minisum path model is effective if the path search can be translated into the conventional least-cost path problem, which aims to find a path with the minimum cost-weighted length between two terminuses on a ratio-scaled raster cost surface, but the minimax (or maximin) path model is mathematically sounder if the cost values are measured on an ordinal scale and practically useful if the problem is concerned not with the minimization of cost but with the maximization of some desirable condition such as suitability.Planerare som arbetar bland annat med att fatta beslut som hänsyftar till vissa lokaler använder ofta rasterbaserade geografiska informationssystem (GIS) för att sätta ett värde på marken med avseende på lämplighet eller kostnad för en viss användning. Ur en beräkningssynpunkt kan denna process ses som en transformation av en eller flera uppsättningar värden associerade med ett rutnät av celler till en annan uppsättning sådana värden genom en funktion som återspeglar ett eller flera kriterier. Medan det generellt förväntas att olika omvandlingar leder till olika "bästa" platser, har lite varit känt om hur sådana skillnader uppstår (eller inte uppstår). Exempel på sådana rumsliga beslutsproblem kan lätt hittas i litteraturen och många av dem handlar om valet av en uppsättning celler (som markanvändningen övervägs tilldelas) från en rasteryta av lämplighet eller kostnad beroende på kontext. För att underlätta GISs algoritmiska tillvägagångssätt antas det ofta att kvaliteten på uppsättningen av celler kan utvärderas som helhet genom summan av deras cellvärden. Giltigheten av detta antagande måste emellertid ifrågasättas om dessa värden mäts på en skala som inte tillåter aritmetiska transformationer. Användning av ordinal skala enligt Stevens typologi är ett exempel av detta. En fråga uppstår naturligt: Finns det ett mer matematiskt sunt och konsekvent tillvägagångssätt för att utvärdera kvaliteten på en rutt när kvaliteten på varje cell i det givna rutnätet mäts med ordinalskala? Avhandlingen försöker svara på ovanstående frågor i samband med ruttplanering genom en serie beräkningsexperiment med hjälp av ett antal slumpmässigt genererade landskapsnät med en rad olika rumsliga och icke-rumsliga strukturer. I den första uppsättningen experiment genererade vi minsta-kostnad rutter på ett antal kostnadsnät som transformerats från landskapsnätverket med hjälp av en mängd olika transformationsparametrar, och analyserade lägen och de (viktade) längderna för dessa rutter. Resultaten visar att samma par ändpunkter mycket väl kan vara sammanbundna med olika minsta-kostnad banor på olika kostnadsraster härledda från samma landskapsraster, och att variationen mellan dessa banor påverkas av hur givna värden fördelas i landskapsrastret såväl som av hur härledda värden fördelas i kostnadsrastret. Mest signifikant är att variationen tenderar att vara mindre när landskapsrastret innehåller mer distinkta grupper av celler som potentiellt lockar eller distraherar kostnadsbesparande passage, eller när kostnadsrastret innehåller ett mindre antal låg-kostnad celler. Den andra uppsättningen experiment syftar till att jämföra två optimeringsmodeller, minisum och minimax (eller maximin) sökmodeller, vilka sammanställer värdena för cellerna som är associerade med en sökväg med summanfunktionen respektive maximum (eller minimum) funktionen. Resultaten tyder på att minisumbanemodellen är effektiv om sökningen av sökvägen kan översättas till det konventionella minsta kostnadsproblemet, vilket syftar till att hitta en väg med den minsta kostnadsvägda längden mellan två terminaler på en ratio-skalad rasterkostyta, men minimax (eller maximin) banmodellen är matematiskt sundare om kostnadsvärdena mäts i ordinär skala och praktiskt användbar om problemet inte bara avser minimering av kostnad men samtidigt maximering av någon önskvärd egenskap såsom lämplighet.
QC 20181002
42
Lanthier, Mark. "Shortest path problems on polyhedral surfaces." Thesis, National Library of Canada = Bibliothèque nationale du Canada, 2000. http://www.collectionscanada.ca/obj/s4/f2/dsk1/tape3/PQDD_0019/NQ48348.pdf.
Full text
43
Dean, Brian C. (Brian Christopher) 1975. "Continuous-time dynamics shortest path algorithms." Thesis, Massachusetts Institute of Technology, 1999. http://hdl.handle.net/1721.1/80530.
Full textAbstract:
Thesis (S.B. and M.Eng.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 1999.Includes bibliographical references (p. 116-117).
by Brian C. Dean.
S.B.and M.Eng.
44
Hua, Liyan. "Shortest Path - Capacitated Maximum Covering Problems." The Ohio State University, 2010. http://rave.ohiolink.edu/etdc/view?acc_num=osu1275477591.
Full text
45
Hojnacki, Susan M. "Optimizing algorithms for shortest path analysis /." Online version of thesis, 1991. http://hdl.handle.net/1850/11143.
Full text
46
Lanthier, Mark (Mark Anthony) Carleton University Dissertation Computer Science. "Shortest path problems on polyhedral surfaces." Ottawa, 1999.
Find full text
47
Glenn, Andrew M. 1978. "Algorithms for the shortest path problem with time windows and shortest path reoptimization in time-dependent networks." Thesis, Massachusetts Institute of Technology, 2001. http://hdl.handle.net/1721.1/86701.
Full textAbstract:
Thesis (M.Eng. and S.B.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2001.Includes bibliographical references (leaves 103-104).
by Andrew M. Glenn.
M.Eng.and S.B.
48
Gray, Chris. "Shortest paths on uncertain terrains." Thesis, 2004. http://hdl.handle.net/2429/15691.
Full textAbstract:
In this dissertation, we introduce the concept of uncertain terrains first suggested by Jorg
Sack. We then examine the problem of finding the shortest path that stays on these terrains
given certain assumptions about the terrains. We show that this problem is NP-hard
under two fairly natural assumptions (meaning that we do not expect any polynomial time
algorithm that finds these paths to be discovered).
49
"An auction algorithm for shortest paths." Massachusetts Institute of Technology, Laboratory for Information and Decision Systems, 1990. http://hdl.handle.net/1721.1/3222.
Full text
50
"Polynomial auction algorithms for shortest paths." Massachusetts Institute of Technology, Laboratory for Information and Decision Systems], 1992. http://hdl.handle.net/1721.1/3264.
Full textAbstract:
by Dimitri P. Bertsekas, Stefano Pallottino, and Maria Grazia Scutella.Includes bibliographical references (p. 24-25).
Supported by NSF. DDM-8903385 Supported by the ARO. C DAAL03-86-K-0171 Supported by a CNR-GNIM grant, and by a Fullbright grant.