École Nationale Supérieure de
Techniques Avancées

Résumé

Les préoccupations environnementales actuelles rendent la réorganisation de nombreux secteurs industriels nécessaire, et en particulier celle du secteur des transports. Avec l'émergence de nouvelles technologies de véhicules et de politiques environnementales, les opérateurs de flottes sont confrontés à une transition: ils doivent choisir la composition de leur flotte et leurs activités quotidiennes, au meilleur coût financier et présentant la plus faible empreinte carbone. Avec pour objectif lointain de créer un outil d'aide à la décision pour les opérateurs de flottes, ce travail aborde un exemple particulier de problème de tournées de véhicules électriques, avec fenêtres temporelles et activités de pick-up et delivery. Nous proposons une formulation du problème en tant que programme linéaire en développant un modèle de multiplication de nœuds, et une approche heuristique. Cette approche heuristique s'articule autour d'un algorithme de labeling créant des tournées élémentaires et d'un oracle, formant un algorithme glouton naturel.