Présentation : http://igm.univ-mlv.fr/AlgoB/slides/LabexBezout/20121003-Meunier.pdf
Colloque Bézout du 23 octobre 2012
Frédéric Meunier (École des Ponts ParisTech, CERMICS)
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.
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.
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.
Travail résultant d’une collaboration avec Daniel Chemla, Roberto Wolfler Calvo, et divers étudiants en stage
