Energy is a limited source in wireless sensor networks and in most applications, it is non-renewable / so designing energy-effcient communication patterns is very important. In this thesis, we de

Disasters (e.g. earthquakes) and emergencies (e.g. fire) threaten the safety of occupants in the buildings and cause injuries and mortalities. These harmful effects are even more dangerous when secondary hazards (e.g. post-earthquake fires) emerge and it is commonly observed that the disasters/emergencies trigger secondary hazards.An effective indoor emergency guidance and navigation approach for occupants and first responders can decrease the number of injuries and mortalities during building emergencies by improving the evacuation process and response operations. For this reason, this research will propose a model-based guidance and vulnerability assessment approach for facilities that are under the threat of multi-hazard emergencies. The approach can be used to guide occupants from the facility affected by disasters/emergencies to safer zones and to direct the first responders by supplying them necessary building related information such as identified vulnerable locations in the indoor environments. An integrated utilization of Building Information Modeling tools, sensors, shortest path algorithms, and vulnerability assessment algorithms is proposed for the system in this research. The research steps of this thesis include (1) determination of requirements of an indoor navigation during emergency response and disaster management,(2) review, comparison, and evaluation of shortest path algorithms from an emergency response and disaster management point of view, (3) proposing a vulnerability assessment approach, and (4) proposing a real-time indoor emergency guidance and navigation system framework for buildings under the threat of multi-hazard emergencies. The findings of the research can be used in future studies on emergency response and disaster management domains.

L’utilisation des réseaux de transport est conditionnée par l’efficacité et la simplicité de leur utilisation. En réponse à une mobilité exacerbée, volontaire ou subie, l’offre de transport se développe et motive tout à la fois, en un cycle continu, des déplacements encore plus exigeants. De manière complémentaire, la mobilité est bousculée par l’arrivée de nouvelles modalités de transport pouvant faire émerger, comme dans le cadre du covoiturage, des acteurs ou des pratiques jusqu’alors inexistants. Si la technologie permet de suivre cette évolution dans les services d’information aux voyageurs, il reste toujours à satisfaire des attentes déterminées par des usages en constante évolution. C’est de ce point de vue que l’obtention de chemins multiples pour relier une origine à une destination est un facteur qui n’est plus à négliger, surtout dans des réseaux de transport denses et comportant de nombreux modes et lignes de transport. Une liberté dans le choix laissé à l’utilisateur du réseau réduit les sentiments d’exclusion, d’incompréhension ou d’anxiété qui peuvent survenir face à une application logicielle ou sur internet et qui effectuent des choix arbitraires de façon autoritaire. De plus, cela permet de vérifier la qualité de l’offre de transport, car plus il existe de moyens différents pour effectuer un trajet dans un intervalle de temps donné, meilleur est le service. Cette thèse s’intéresse au calcul de telles alternatives par le biais de l’énumération par coût croissant des chemins entre deux points, puis par le filtrage de ceux-ci suivant des critères, supposés quelconques et laissés à l’appréciation des professionnels de transport qui peuvent ainsi faire varier les angles d’analyses de leurs offres.Par ailleurs, la synchronisation de trajets de plusieurs utilisateurs, en vue d’usages sociaux ou de déplacements mutualisés, est étudiée dans ce manuscrit sous l’angle du covoiturage. En ne considérant que deux usagers, l’objectif est de minimiser le temps de trajet global des participants sous la contrainte qu’ils partagent une partie de leur chemin entre un point de rencontre et un point de séparation qu’il faut alors déterminer. Sont également étudiées les variantes associées au changement des conditions de transport de chacun des participants comme l’établissement d’une origine ou d’une destination commune parallèlement à des contraintes sur les heures de départ ou d’arrivée des usagers. Enfin, puisque la voiture est très souvent pénalisée par la prise en charge d’un piéton, il convient d’étudier comment ce détour peut être contraint et les impacts sur les gains que cette limitation engendre.Cette thèse a été réalisée dans un contexte CIFRE pour la société MobiGIS. Lestravaux qui s’y rapportent ont fait l’objet de réalisations pratiques tant pour fournirdes solutions de mobilité dans le cadre des activités de l’entreprise que pour évaluerexpérimentalement les performances des algorithmes proposés pour les résoudre. / Efficiency and simplicity are two conditions upon which the use of a transportation system is relevant. May it be intentional or imposed, an increasing mobility triggers the need to enhance the transportation offer. In turn, such a response encourages an even more demanding mobility in a constantly adapting cycle. In parallel, new and forthcoming means of transportation emerge from time to time with unknown practices and renewed actors : exactly like what carpooling is stirring at the moment. Passenger information systems can technically deal with such evolutions thanks to improved technologies but they still struggle to keep up with constantly changing usage expectations.From this perspective the computation of several paths from an origin to a destination becomes increasingly relevant. This issue is even more crucial in dense transportation networks in which many modes and lines of transportation are combined. Indeed, giving some traveling choices to the end user reduces the feeling of exclusion, anxiety and the lack of understanding which may arise when facing arbitrary decisions dictated by a software or an Internet application. It is also helpful to estimate the quality of the transportation offer since the more paths exist to go from point A to point B within a fixed time window, the better the service is. This thesis focuses on the computation of such alternatives by the gradually increasing enumeration of paths between two points. Given this input, the pruning necessary to obtain such a diverse selection is assumed not to be known in advance. It is left up to transportation professionals who may choose a fitted solution based on their specific knowledge and objectives.Another subject studied in this thesis concerns the itinerary synchronization of several users for various social uses such as shared travels. It is here seen from the perspective of carpooling. Considering only two users, the problem is to minimize the traveling cost of the users under the constraint that they must share some part of their respective trips with one another. Solving this problem is equivalent to finding a pick up point and a drop off location between which both paths overlap. Multiple corner cases concerning the transportation conditions of each user as well as the special cases of shared origins or destinations are studied. The constraints on the arrival and/or departure times may also vary. Last but not least and since the driver is often penalized when giving up a lift, the restriction to a maximal detour the driver accepts, compared to his shortest path, is analyzed with respect to the benefits such a limitation generates.This thesis was funded by the MobiGIS company under the CIFRE (Industrial Agreement of Training through Research) researching context. The related work consisted in the practical implementation of mobility solutions within the framework of the company as well as the experimental performances evaluation of the algorithms proposed to solve them.

Dans cette thèse, nous étudions plusieurs modèles de routage efficaces en énergie. Pour chaque modèle, nous présentons une formulation en programmation linéaire mixte permettant de trouver une solution exacte. En outre, comme il s’agit de problèmes NP-Difficiles, nous proposons des heuristiques efficaces pour des réseaux de grande taille. Dans la première partie de cette thèse, nous étudions une solution de routage efficace en énergie dans laquelle nous ajoutons la possibilité d’éliminer des redondances dans les paquets transmis sur le réseau. Nous montrons premièrement que l’ajout de l’élimination des redondances permet d’améliorer l’efficacité énergétique des réseaux en éteignant plus de liens. Ensuite, nous étendons le modèle afin qu’il prenne en compte un certain niveau d’incertitudes dans le volume de trafic et le taux de redondances. La deuxième partie de cette thèse est consacrée aux problèmes qui se posent lors du déploiement de tels protocoles dans les réseaux. Plus particulièrement, nous proposons de minimiser les changements entre deux configurations réseaux consécutives lorsque plusieurs matrices de trafic sont considérées. Le routage des demandes étant alors assuré avec le protocole de routage OSPF (Open Shortest Path First). Ensuite, nous abordons le problème de la limitation du nombre de règles de routage dans les routeurs en utilisant une technologie de type SDN (Software Defined Networks). Enfin, nous présentons en annexe des travaux complémentaires réalisés au cours de cette thèse concernant le routage multicast et le contrôle de congestion TCP. / In this thesis, we study several models of energy-Aware routing. For each model, we present a linear programming formulation to find the exact solution. Moreover, since energy-Aware routing is NP-Hard problem, we also propose efficient heuristic algorithms for large scale networks. In the first part of this thesis, we deal with GreenRE - a new energy-Aware routing model with the support of redundancy elimination. We first present a deterministic model in which we show how to combine energy-Aware routing and redundancy elimination to improve energy efficiency for backbone networks. Then, we extend the model in order to take into account uncertainties in traffic volumes and redundancy rates. The second part of this thesis is devoted to the deployment issues of energy- aware routing in practice. In detail, to avoid service deterioration for end-Users, we limit changes of network configurations in multi-Period traffic matrices in Open Shortest Path First (OSPF) protocol. Next, we address the problem of limited rule space in OpenFlow switches when installing energy-Aware routing configurations. Finally, we present in the appendix other works developed during this thesis: multicast network protocol and TCP congestion control algorithm.

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.