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 distancier / This 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

京都大学 / 0048 / 新制・課程博士 / 博士(工学) / 甲第21361号 / 工博第4520号 / 新制||工||1704(附属図書館) / 京都大学大学院工学研究科都市社会工学専攻 / (主査)教授 山田 忠史, 教授 藤井 聡, 准教授 SCHMOECKER,Jan-Dirk / 学位規則第4条第1項該当 / Doctor of Philosophy (Engineering) / Kyoto University / DFAM

We address the problem of all-pairs shortest time communication of messages in futuregeneration 6G networks by modeling the highly dynamic characteristics of the network using a temporal graph. Based on this model, an elegant technique is proposed to devise an algorithm for finding the all-pairs shortest time paths in the temporal graph that can be used for all-pairs internodes communication of messages in the network. The proposed algorithm basically involves computations similar to only two matrix multiplication steps, once in the forward direction and then in the backward direction.

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.

No description available.

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.

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

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

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

O Problema dos K Menores Caminhos é uma generalização do Problema do Menor Caminho, em que desejamos encontrar os K caminhos de menor custo entre dois vértices de um grafo. Estudamos e implementamos algoritmos que resolvem esse problema em grafos dirigidos, com peso nos arcos e que permitem apenas caminhos sem repetição de vértices na resposta. Comparamos seus desempenhos utilizando grafos do 9th DIMACS Implementation Challenge. Identificamos os pontos fortes e fracos de cada algoritmo, e propusemos uma variante híbrida dos algoritmos de Feng e de Pascoal. Essa variante proposta obteve desempenho superior aos algoritmos base em alguns grafos, e resultado superior a pelo menos um deles na grande maioria dos testes. / The K-Shortest Path Problem is a generalization of the Shortest Path Problem, in which we must find the K paths between two vertices in a graph that have the lowest costs. We study some K-Shortest Path Problem algorithms applied to weighted directed graphs, allowing only paths with no repeated vertices. We compare empirically implementation of some algorithms, using instance graphs from the 9th DIMACS Implementation Challenge. We identify the strengths and weaknesses of each algorithm, and we propose a hybrid version of Feng\'s and Pascoal\'s algorithms. This proposed variant achieve better perfomance compared to both base algorithms in some graphs, and it is better than at least one of them in most cases.