Adoption of electric vehicles has been restrained by the availability of charging stations and consumer fear of being stranded with a depleted battery, far from the nearest charger. In many areas of the world, charging stations are now widely available and the transition from vehicles with internal combustion engines is accelerating, though still in a fairly early stage. For electric vehicle drivers in those areas, anxiety that they will not be able to find a charger (“range anxiety”) is subsiding. However, differences in charging speed and pricing between stations and different outlets at the same station can be large. Total trip duration can vary significantly based on the charging outlet selected. Prior research has developed methods for helping all drivers find the fastest route and for electric vehicle drivers to ensure that they are able to complete their trip. Additional research has explored other complexities of route selection for electric vehicles such as how to select optimal stations for charging based on the total trip duration, including driving and charging time. Pricing for recharging electric vehicles at public chargers is more complex and diverse than for gas filling stations due to the differences in charging rates and the relatively low competition. This research investigates those differences. Using design science research methodology, a method is presented for determining which charging stops result in the lowest possible charging cost for a given route. The method is demonstrated through experiment with random routes within Sweden. The experimental results show that the average cost savings as compared to the duration-optimal route is 15% and 139 SEK per additional hour of trip time. One possible direction for future work is to improve the performance of the algorithm for use in real-time consumer route planning applications.

As the interest in electric heavy-duty vehicles has grown, so has the need for route planning tools to coordinate fleets of electric vehicles. This problem is called the Electric Vehicle Routing Problem (EVRP) and it can be solved using a Branch-Price-and-Cut method, where routes for individual vehicles are iteratively generated using information from the coordinated problem. These routes are computed in a pricing problem, which is a Resource Constrained Elementary Shortest Path Problem (RCESPP). Because of its iterative nature, the Branch-Price-and-Cut method is dependent on a fast solver for this RCSPP to get a good computational performance. In this thesis, we have implemented a labeling algorithm for the RCESSP for electric vehicles with state-of-the-art acceleration strategies. We further suggest a new bounding method that exploits the electric aspects of the problem. The algorithm's performance and the effect of the different acceleration strategies are evaluated on benchmark instances for the EVRP, and we report significantly improved computational times when using our bounding method for all types of instances. We find that route relaxation methods (ng-routes) were particularly advantageous in test instances with a combination of clustered and randomly distributed customers. Interestingly, for test instances with only randomly distributed customers, ng-relaxation required longer processing time to achieve elementary optimal routes and for these instances, the bounding methods gave better computational performance.

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

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

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

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

The Constrained Shortest Path Problem (CSPP) consists of finding the shortest path in a graph or network that satisfies one or more resource constraints. Without these constraints, the shortest path problem can be solved in polynomial time; with them, the CSPP is NP-hard and thus far no polynomial-time algorithms exist for solving it optimally. The problem arises in a number of practical situations. In the case of vehicle path planning, the vehicle may be an aircraft flying through a region with obstacles such as mountains or radar detectors, with an upper bound on the fuel consumption, the travel time or the risk of attack. The vehicle may be a submarine travelling through a region with sonar detectors, with a time or risk budget. These problems all involve a network which is a discrete model of the physical domain. Another example would be the routing of voice and data information in a communications network such as a mobile phone network, where the constraints may include maximum call delays or relay node capacities. This is a problem of current economic importance, and one for which time-sensitive solutions are not always available, especially if the networks are large. We consider the simplest form of the problem, large grid networks with a single side constraint, which have been studied in the literature. This thesis explores the application of Constraint Programming combined with Lagrange Relaxation to achieve optimal or near-optimal solutions of the CSPP. The following is a brief outline of the contribution of this thesis. Lagrange Relaxation may or may not achieve optimal or near-optimal results on its own. Often, large duality gaps are present. We make a simple modification to Dijkstra’s algorithm that does not involve any additional computational work in order to generate an estimate of path time at every node. / We then use this information to constrain the network along a bisecting meridian. The combination of Lagrange Relaxation (LR) and a heuristic for filtering along the meridian provide an aggressive method for finding near-optimal solutions in a short time. Two network problems are studied in this work. The first is a Submarine Transit Path problem in which the transit field contains four sonar detectors at known locations, each with the same detection profile. The side constraint is the total transit time, with the submarine capable of 2 speeds. For the single-speed case, the initial LR duality gap may be as high as 30%. The first hybrid method uses a single centre meridian to constrain the network based on the unused time resource, and is able to produce solutions that are generally within 1% of optimal and always below 3%. Using the computation time for the initial Lagrange Relaxation as a baseline, the average computation time for the first hybrid method is about 30% to 50% higher, and the worst case CPU times are 2 to 4 times higher. The second problem is a random valued network from the literature. Edge costs, times, and lengths are uniform, randomly generated integers in a given range. Since the values given in the literature problems do not yield problems with a high duality gap, the values are varied and from a population of approximately 100,000 problems only the worst 200 from each set are chosen for study. These problems have an initial LR duality gap as high as 40%. A second hybrid method is developed, using values for the unused time resource and the lower bound values computed by Dijkstra’s algorithm as part of the LR method. The computed values are then used to position multiple constraining meridians in order to allow LR to find better solutions. / This second hybrid method is able to produce solutions that are generally within 0.1% of optimal, with computation times that are on average 2 times the initial Lagrange Relaxation time, and in the worst case only about 5 times higher. The best method for solving the Constrained Shortest Path Problem reported in the literature thus far is the LRE-A method of Carlyle et al. (2007), which uses Lagrange Relaxation for preprocessing followed by a bounded search using aggregate constraints. We replace Lagrange Relaxation with the second hybrid method and show that optimal solutions are produced for both network problems with computation times that are between one and two orders of magnitude faster than LRE-A. In addition, these hybrid methods combined with the bounded search are up to 2 orders of magnitude faster than the commercial CPlex package using a straightforward MILP formulation of the problem. Finally, the second hybrid method is used as a preprocessing step on both network problems, prior to running CPlex. This preprocessing reduces the network size sufficiently to allow CPlex to solve all cases to optimality up to 3 orders of magnitude faster than without this preprocessing, and up to an order of magnitude faster than using Lagrange Relaxation for preprocessing. Chapter 1 provides a review of the thesis and some terminology used. Chapter 2 reviews previous approaches to the CSPP, in particular the two current best methods. Chapter 3 applies Lagrange Relaxation to the Submarine Transit Path problem with 2 speeds, to provide a baseline for comparison. The problem is reduced to a single speed, which demonstrates the large duality gap problem possible with Lagrange Relaxation, and the first hybrid method is introduced. / Chapter 4 examines a grid network problem using randomly generated edge costs and weights, and introduces the second hybrid method. Chapter 5 then applies the second hybrid method to both network problems as a preprocessing step, using both CPlex and a bounded search method from the literature to solve to optimality. The conclusion of this thesis and directions for future work are discussed in Chapter 6.

The thesis is focused on solving the Sokoban game using artificial intelligence algorithms. The first part of the thesis describes the Sokoban game, state space and selected state space search methods. In the second part selected methods were implemented and graphic user interface was created in the Python environment. Comparative experiments were executed in the final part.

Devido a restrições de aplicabilidade presentes nos algoritmos para a solução de problemas de otimização combinatória, os sistemas baseados em redes neurais artificiais e algoritmos genéticos oferecem um método alternativo para solucionar tais problemas eficientemente. Os algoritmos genéticos devem a sua popularidade à possibilidade de percorrer espaços de busca não-lineares e extensos. Já as redes neurais artificiais possuem altas taxas de processamento por utilizarem um número elevado de elementos processadores simples com alta conectividade entre si. Complementarmente, redes neurais com conexões realimentadas fornecem um modelo computacional capaz de resolver vários tipos de problemas de otimização, os quais consistem, geralmente, da otimização de uma função objetivo que pode estar sujeita ou não a um conjunto de restrições. Esta tese apresenta uma abordagem inovadora para resolver problemas de conexão em otimização combinatória utilizando uma arquitetura neuro-genética. Mais especificamente, uma rede neural de Hopfield modificada é associada a um algoritmo genético visando garantir a convergência da rede em direção aos pontos de equilíbrio factíveis que representam as soluções para os problemas de otimização combinatória. / Due to applicability constraints involved with the algorithms for solving combinatorial optimization problems, systems based on artificial neural networks and genetic algorithms are alternative methods for solving these problems in an efficient way. The genetic algorithms must its popularity to make possible cover nonlinear and extensive search spaces. On the other hand, artificial neural networks have high processing rates due to the use of a massive number of simple processing elements and the high degree of connectivity between these elements. Additionally, neural networks with feedback connections provide a computing model capable of solving a large class of optimization problems, which refer to optimization of an objective function that can be subject to constraints. This thesis presents a novel approach for solving connection problems in combinatorial optimization using a neurogenetic approach. More specifically, a modified Hopfield neural network is associated with a genetic algorithm in order to guarantee the convergence of the network to the equilibrium points, which represent feasible solutions for the combinatorial optimization problems.

Submitted by William Justo Figueiro (williamjf) on 2015-07-21T22:37:51Z No. of bitstreams: 1 63c.pdf: 2699232 bytes, checksum: 1ae2013ef31101508f9fef3997d71790 (MD5) / Made available in DSpace on 2015-07-21T22:37:51Z (GMT). No. of bitstreams: 1 63c.pdf: 2699232 bytes, checksum: 1ae2013ef31101508f9fef3997d71790 (MD5) Previous issue date: 2013 / SIMTUR - Sistema Inteligente De Monitoramento de Tráfego Urbano / O crescente aumento do uso de automóveis e de motocicletas tem provocado uma contínua degradação no trânsito urbano das grandes metrópoles. Este cenário é agravado pelas deficiências nos atuais sistemas de transporte público, geradas, em parte, pela falta de informação ao usuário. O presente trabalho apresenta um modelo computacional para um sistema de informação ao usuário de transporte público. Ao contrário de outros trabalhos baseados no algoritmo clássico Dijkstra, a abordagem apresentada faz uso do algoritmo A* para resolução do problema de caminhos mínimos, presente neste contexto, a fim de reduzir o tempo de resposta de maneira que o modelo possa ser utilizado em um sistema real de informação ao usuário. O modelo proposto considera múltiplos critérios de decisão, como a distância total percorrida e o número de transbordos. Um estudo de caso foi realizado utilizando dados reais do transporte público da cidade Porto Alegre com o objetivo de avaliar o modelo computacional desenvolvido. Os resultados gerados foram comparados com aqueles obtidos através do emprego do algoritmo Dijkstra e indicam que a combinação do algoritmo A* com técnicas de aceleração permite reduzir, significativamente, a complexidade de espaço, o tempo de processamento e o número de transbordos. / The increasing use of automobiles and motorcycles has caused a continuous degradation in the traffic of large cities. This scenario gets worse due to shortcomings in the current public transportation, which is entailed, in a certain way, by the lack of information provided to the user. This study shows a computing model for a public transportation user information system. Unlike other studies based on the classical Dijkstra’s algorithm, the approach makes use of the algorithm A* to solve a shortest path problem to reduce the response time so that the model can be used in an real-time web information system. The proposed model takes into account multiple criteria of decision, such as total distance traveled and number of transfers and it was evaluated with data from Porto Alegre’s public transportation. The results were compared to those ones obtained by the use of Dijkstra’s algorithm and indicate that the combination of algorithm A* with acceleration techniques allows reducing significantly the space complexity, processing time and the number of transfers.