L’autopartage est une manière moderne de louer une voiture. C'est un système attractif pour les clients qui utilisent une voiture occasionnellement. Dans un système d’autopartage, une flotte de véhicules est répartie sur une aire urbaine. Les client peuvent prendre ou rendre une voiture à n'importe quel moment et à n'importe quelle station, à condition qu’il y ait une voiture de libre à la station de départ et qu’il y a une place de parking libre à la station de destination. Pour s'en assurer, les clients peuvent réserver une voiture en avance. Pour qu’un tel système fonctionne de manière satisfaisante, il faut que le nombre de véhicules et le nombre de places libres dans les stations s'équilibrent. Cela conduit à un problème d'équilibre d'occupation des stations, appelé problème de relocalisation : un opérateur doit surveiller l'occupation des stations et décider quand et de quelle manière les voiture doivent être deplacées d’une station « trop pleine » à une station « insuffisamment pleine ». Nous considérons un système d’autopartage innovant, où les voitures sont partiellement autonomes. Cela permet de constituer des convois de véhicules que dirige un véhicule spécial, de sorte qu'un convoi est mis en mouvement par un seul conducteur. Cette configuration est similaire au système mis en place pour les vélos en libre-service, où un camion peut déplacer plusieurs vélos simultanément pendant le processus de la relocalisation. Dans le cadre de cette thèse, nous développons les aspects dynamiques et statiques du problème de relocalisation. Le « problème de relocalisation dynamique » décrit la situation où les voitures sont déplacées pendant les heures de travail afin de satisfaire les besoins des clients. L’opérateur doit prendre des décisions « dynamiques », en fonction de la situation. Dans le cadre du « problème de relocalisation statique », nous supposons qu’il n'y a aucune interaction (ou très peu) entre les clients et le système. Cette situation se produit lorsque le système est préparé pour le lendemain (ex : processus de la relocalisation effectué pendant la nuit). Nous modélisons le problème de relocalisation dans le cadre d’un système de tâches métriques. Ensuite, nous analysons les deux problèmes et nous donnons des stratégies pour les résoudre. Enfin, nous effectuons quelques expériences de calcul pour examiner l’applicabilité des algorithmes présentés en pratique. / Carsharing is a modern way of car rental, attractive to customers who make only occasional use of a car on demand. In a carsharing system, a fleet of cars is distributed at specified stations in an urban area, customers can take a car at any time and station and return it at any time and station, provided that there is a car available at the start station and a free place at the destination station. To ensure the latter, customers have to book their demands in advance. For operating such a system in a satisfactory way, the stations have to keep a good ratio between the total number of places and the number of cars in each station, in order to serve as many requests as possible. This leads to the problem of balancing the load of the stations, called Relocation Problem: an operator has to monitor the load and to decide when and how to move cars from “overfull” stations to “underfull” ones. We consider an innovative carsharing system, where the cars are partly autonomous, which allows to build wireless convoys of cars leaded by a special vehicle, such that the whole convoy is moved by only one driver. This setting is similar to bikesharing, where trucks can simultaneously move several bikes during the relocation process. In this thesis, we address the dynamic and static aspects of the Relocation Problem. The “Dynamic Relocation Problem” describes the situation when cars can be moved between stations during the working hours in order to satisfy the needs of the customers. Hereby, the operator has to make decisions dynamically according to the current situation. In the “Static Relocation Problem” we assume that there is no (or only little) interaction by customers with the system. This situation occurs when the carsharing system is prepared for the next day, i.e., the relocation process is performed during the night. We model the Relocation Problem in the framework of a metric task system. Afterwards, we theoretically analyze both problems and give strategies to solve them. Finally, we perform some computational experiments to examine the applicability of the presented algorithms in practice.

No description available.

La forte variabilité des trafics est devenue l'un des problèmes majeurs auxquels doivent faire face les gestionnaires d'infrastructures réseau. Dans ces conditions, l'optimisation du routage des flux en se basant uniquement sur une matrice de trafic moyenne estimée en heure de pointe n'est plus pertinente. Les travaux conduits dans cette thèse visent la conception de méthodes d'optimisation dynamiques du routage, adaptant en temps réel les routes utilisées par les flux aux conditions de trafic dans le réseau.Nous étudions tout d'abord le problème d'optimisation des poids OSPF pour le routage intra-domaine dans les réseaux IP, où le trafic est routé le long de plus courts chemins, en fonction des poids des liens. Nous proposons une approche en ligne permettant de reconfigurer dynamiquement les poids OSPF, et donc les routes utilisées, pour répondre aux variations observées du trafic et réduire ainsi le taux de congestion du réseau. L'approche proposée repose sur l'estimation robuste des demandes en trafic des flux à partir de mesures SNMP sur la charge des liens. Les résultats expérimentaux, aussi bien sur des trafics simulés que réels, montrent que le taux de congestion du réseau peut être significativement réduit par rapport à une configuration statique.Dans la même optique, nous nous intéressons également à l'optimisation des réseaux MPLS, qui permettent de gérer l'utilisation des ressources disponibles en affectant un chemin spécifique à chaque LSP. Nous proposons un algorithme inspiré de la théorie des jeux pour déterminer le placement des LSP optimisant un critère de performance non linéaire. Nous établissons la convergence de cet algorithme et obtenons des bornes sur son facteur d'approximation pour plusieurs fonctions de coût. L'intérêt principal de cette technique étant d'offrir des solutions de bonne qualité en des temps de calcul extrêmement réduits, nous étudions son utilisation pour la reconfiguration dynamique du placement des LSP.La dernière partie de cette thèse est consacrée à la conception et au développement d'une solution logicielle permettant le déploiement d'un réseau overlay auto-guérissant et auto-optimisant entre différentes plateformes de cloud computing. La solution est conçue pour ne nécessiter aucun changement des applications. En mesurant régulièrement la qualité des liens Internet entre les centres de données, elle permet de détecter rapidement la panne d'une route IP et de basculer le trafic sur un chemin de secours. Elle permet également de découvrir dynamiquement les chemins dans le réseau overlay qui optimisent une métrique de routage spécifique à l'application. Nous décrivons l'architecture et l'implémentation du système, ainsi que les expériences réalisées à la fois en émulation et sur une plateforme réelle composée de plusieurs centres de données situés dans différents pays. / The high variability of traffic has become one of the major problems faced by network infrastructure managers . Under these conditions, flow route optimization based solely on an average busy hour traffic matrix is no longer relevant. The work done in this thesis aims to design dynamic routing optimization methods, adapting in real time the routes used by the flows to the actual network traffic conditions.We first study the problem of OSPF weight optimization for intra-domain routing in IP networks, where the traffic is routed along shortest paths, according to links weights. We propose an online scheme to dynamically reconfigure the OSPF weights and therefore the routes used, to respond to observed traffic variations and reduce the network congestion rate. The proposed approach is based on robust estimation of flow traffic demands from SNMP measurements on links loads. Experimental results, both on simulated and real traffic data show that the network congestion rate can be significantly reduced in comparison to a static weight configuration.On the same idea, we are also interested in optimizing MPLS networks that manage the available resource utilization by assigning a specific path for each LSP. We propose an algorithm inspired by game theory to determine the LSP placement optimizing a nonlinear performance criterion. We establish the convergence of the algorithm and obtain bounds on its approximation factor for several cost functions. As the main advantage of this technique is to offer good quality solutions in extremely reduced computation times, we are studying its use for dynamic reconfiguration of the LSP placement.The last part of this thesis is devoted to the design and development of a software solution for the deployment of a self-healing and self-optimizing network overlay between different cloud platforms. The solution is designed such that no change is required for client applications. By regularly measuring the quality of Internet links between data centers, it can quickly detect an IP route failure and switch the traffic to a backup path. It also allows to dynamically discover the paths in the overlay network that optimize a routing metric specific to the application. We describe the system architecture and implementation, as well as the experiments in both emulation and real platform composed of several data centers located in different countries

京都大学 / 0048 / 新制・課程博士 / 博士(情報学) / 甲第19123号 / 情博第569号 / 新制||情||100(附属図書館) / 32074 / 京都大学大学院情報学研究科数理工学専攻 / (主査)教授 山下 信雄, 教授 中村 佳正, 教授 田中 利幸 / 学位規則第4条第1項該当 / Doctor of Informatics / Kyoto University / DFAM

[pt] Nesse trabalho, propomos o problema AdInvest, que modela o processo decisiório de alocação de investimento em marketing digital do ponto de vista do anunciante. Para o problema proposto, definimos um algoritmo chamado balGreedy, e provamos suas garantias para instâncias determísticas e estocásticas do AdInvest. Os teoremas provados garantem ao nosso algoritmo resultados de pior caso relativamente próximos ao OPT, em diversos tipos de instâncias levantadas ao decorrer do trabalho. Em especial, focamos nas instâncias que modelam o efeito de saturação das audiências, que se faz presente na dinâmica de anúncios online. Como mostrado nos experimentos computacionais, o algoritmo balGreedy se mostrou consistentemente eficiente em comparação com as políticas alternativas adotadas, tanto nas instâncias que foram geradas por simulação, quanto em instâncias reais obtidas a partir de dados de um anunciante do Facebook Ads. / [en] In this work, we propose the problem AdInvest, which models the decision-making process for allocating investment in digital marketing from the advertiser perspective. For the proposed problem, we define an algorithm called balGreedy, and we prove its guarantees in deterministic and stochastic instances of the AdInvest. The proven theorems assure to our algorithm worst-case results relatively close to OPT, in several types of instances raised during the work. In particular, we focus on the instances that model the audience saturation effect, which is present in the dynamics of online advertisements. As shown in the computational experiments, the balGreedy algorithm had been consistently efficient compared to the alternative policies adopted, both in the instances generated by simulation and in real instances built from the data of a certain Facebook Ads advertiser.