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.

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.

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.

The current methods used by forensic experts to analyse blood spatter neglects the influence of gravitation and drag on the trajectory of the droplet. This research attempts to suggest a more accurate method to determine the trajectory of a blood droplet using multi-target tracking. The multi-target tracking problem can be rewritten as a linear programming problem and solved by means of optimization and numerical methods. A literature survey is presented on relevant articles on blood spatter analysis and multi-target tracking. In contrast to a more advanced approach that assumes a background in probability, mathematical modelling and forensic science, this dissertation aims to give a comprehensive mathematical exposition of particle tracking. The tracking of multi-targets, through multi-target tracking, is investigated. The dynamic programming methods to solve the multi-target tracking are coded in the MATLAB programming language. Results are obtained for different scenarios and option inputs. Research strategies include studying documents, articles, journal entries and books. / MSc (Applied Mathematics), North-West University, Potchefstroom Campus, 2014

The current methods used by forensic experts to analyse blood spatter neglects the influence of gravitation and drag on the trajectory of the droplet. This research attempts to suggest a more accurate method to determine the trajectory of a blood droplet using multi-target tracking. The multi-target tracking problem can be rewritten as a linear programming problem and solved by means of optimization and numerical methods. A literature survey is presented on relevant articles on blood spatter analysis and multi-target tracking. In contrast to a more advanced approach that assumes a background in probability, mathematical modelling and forensic science, this dissertation aims to give a comprehensive mathematical exposition of particle tracking. The tracking of multi-targets, through multi-target tracking, is investigated. The dynamic programming methods to solve the multi-target tracking are coded in the MATLAB programming language. Results are obtained for different scenarios and option inputs. Research strategies include studying documents, articles, journal entries and books. / MSc (Applied Mathematics), North-West University, Potchefstroom Campus, 2014

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

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

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.

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.

L'objectif de ce travail de thèse est de proposer des approches algorithmiques permettant de traiter la problématique du routage adaptatif (RA) dans un réseau de communication à trafic irrégulier. L'analyse des algorithmes existants nous a conduit à retenir comme base de travail l'algorithme Q-Routing (QR); celui-ci s'appuie sur la technique d'apprentissage par renforcement basée sur les modèles de Markov. L'efficacité de ce type de routage dépend fortement des informations sur la charge et la nature du trafic sur le réseau. Ces dernières doivent être à la fois, suffisantes, pertinentes et reflétant la charge réelle du réseau lors de la phase de prise de décision. Pour remédier aux inconvénients des techniques utilisant le QR, nous avons proposé deux algorithmes de RA. Le premier, appelé Q-Neural Routing, s'appuie sur un modèle neuronal stochastique pour estimer et mettre à jour les paramètres nécessaires au RA. Afin d'accélérer le temps de convergence, une deuxième approche est proposée : K-Shortest path Q-Routing. Elle est basée sur la technique de routage multi chemin combiné avec l'algorithme QR, l'espace d'exploration étant réduit aux k meilleurs chemins. Les deux algorithmes proposés sont validés et comparés aux approches traditionnelles en utilisant la plateforme de simulation OPNET, leur efficacité au niveau du RA est mise particulièrement en évidence. En effet, ceux-ci permettent une meilleure prise en compte de l'état du réseau contrairement aux approches classiques.