Sélection d'arcs et génération de colonnes pour le problème d'horaires d'autobus électriques

Dans un contexte de changement climatique, il est important de réduire l’émission de gaz à effet de serre. Dans ce but, il est intéressant d’avoir recours à des véhicules électriques, notamment pour les transports en commun. Pour avoir un réseau d’autobus efficace, il est nécessaire de planifier son fonctionnement. Cela peut se faire en résolvant des problèmes d’optimisation. Un de ces derniers est le problème d’horaires de véhicules électriques multidépôts qui est un des problèmes résolus par les solveurs d’optimisation de l’entreprise GIRO qui a financé ce travail. Le problème d’horaires de véhicules électriques a pour objectif de couvrir à moindre coût l’ensemble des trajets journaliers proposés aux usagers à l’aide d’une flotte d’autobus. Pour ce faire, on cherche à assigner à chaque autobus un horaire qui est composé d’une suite de trajets à effectuer en tenant compte des contraintes temporelles et de capacité des batteries électriques des véhicules. Du fait des nouvelles contraintes à prendre en compte pour les véhicules électriques, on ne peut pas utiliser directement les méthodes de résolution du problème classique d’horaires de véhicules. De plus, dans le but d’être au plus proche de la réalité, on choisit de modéliser le processus de recharge des véhicules avec une fonction non-linéaire définie par morceaux. On formule le problème d’horaires de véhicules électriques multi-dépôts comme un programme linéaire en nombres entiers. Une méthode efficace pour le résoudre est d’utiliser la génération de colonnes. Dans l’algorithme de génération de colonnes, on résout à chaque itération des sous-problèmes pour déterminer des nouveaux horaires d’autobus. Un tel sous-problème correspond à un problème de plus court chemin avec contraintes de ressources défini sur un graphe combinant un réseau de connexions et un réseau espace-temps. On associe un coût à chaque arc ainsi qu’une dépense d’énergie.