Les principaux inconvénients actuels pour l'essor du Véhicule Électrique (VE) sont incontestablement le coût et l'autonomie du véhicule ainsi que la disponibilité de l'infrastructure de recharge.

La plupart des travaux de recherche se sont concentrés soit sur l'allocation des tournées au VE soit sur la planification de sa recharge. Aucune étude antérieure ne s'est intéressée à la résolution simultanée des deux problèmes.

Dans cette étude, nous étudions le problème intégré d'allocation des VEs aux tournées et de recharge de ces VEs pour assurer la disponibilité de l'énergie nécessaire pour les tournées. Tout d'abord, nous montrons que ce problème est NP-difficile au sens ordinaire à travers la réduction du problème de Partition à notre problème. Ensuite, nous proposons une heuristique fonctionnant en deux phases. Dans la première phase, nous construisons un graphe pondéré où les nœuds représentent les tournées et sont pondérés par la longueur de celles-ci. Nous exploitons ensuite le problème de clique de poids maximum avec des contraintes supplémentaires pour affecter un ensemble de tournées à un VE avec comme objectif de maximiser son usage et assurer la faisabilité de sa recharge.

Dans la deuxième phase, nous proposons une planification optimisée de la recharge de ce VE en se basant sur le problème de flot à coût minimum et nous répétons le même algorithme (phases 1 et 2) pour l'ensemble des VEs.

D'autre part, nous proposons un programme linéaire en variables mixtes pour optimiser l'allocation et la recharge des VEs. Ce modèle est résolu avec CPLEX.

Les résultats générés par l'heuristique sur plus de 450 instances aléatoires de flottes de véhicules hétérogènes (constituées de véhicules thermiques et de VEs ayant des caractéristiques de batteries différentes) ont été comparés aux résultats de CPLEX.

Dans la plupart des instances, l'heuristique obtient des résultats semblables à Cplex en termes de solution optimale mais aussi des meilleurs résultats pour les instances non résolues à l'optimum et elle réduit considérablement le temps de calcul.