Présentation : http://igm.univ-mlv.fr/AlgoB/slides/LabexBezout/20121003-Meunier.pdf<br /><br />Colloque Bézout du 23 octobre 2012<br />Frédéric Meunier (École des Ponts ParisTech, CERMICS)<br /><br />La régulation des systèmes de vélos partagés, comme Vélib’, soulève de nombreux problèmes opérationnels. L’un des plus naturels est celui du repositionnement des vélos par un ou plusieurs camions.<br />On s’intéresse ici au cas statique, mono-camion. On se donne un réseau dont les sommets sont des stations. On connaît la répartition courante des vélos dans les stations et on veut les déplacer à l’aide d’un camion de manière à atteindre une répartition-cible, et ce, au coût minimum. La motivation opérationnelle correspond à la situation rencontrée en fin de nuit, lorsque quasiment aucun vélo ne se déplace.<br />Une partie de l’exposé traitera des cas particuliers polynomiaux et des algorithmes d’approximation. Une méthode efficace pour résoudre en pratique des instances de taille raisonnable sera également présentée : cette méthode combine le calcul exact d’une borne inférieure naturelle et une recherche locale exploitant certaines propriétés théoriques du problème. Enfin, des questions ouvertes seront discutées.<br /><br />Travail résultant d’une collaboration avec Daniel Chemla, Roberto Wolfler Calvo, et divers étudiants en stage
