Redéploiement en convois de flottes de véhicules partagés

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.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