Planification d’autocars

La planification des véhicules intervient dans le transport routier de voyageurs. Le problème consiste à affecter des véhicules aux courses en minimisant les ressources utilisées. Une course correspond à une mission de transport. Elle est définie par des lieux et horaires de départ et d’arrivée.

Données

Les données d’entrée pour le problème de planification des véhicules sont les suivantes :
 des courses commerciales pour lesquelles sont spécifiés le nombre de places nécessaires et la catégorie de véhicule requise ;
 des véhicules répartis sur différents dépôts de capacité finie ;
 les temps de trajets entre tous les lieux impliqués dans le problème. Ces temps de trajet ont été calculés au moyen d’un système d’information géographique (SIG).

Contraintes

Un planning réalisable doit satisfaire quatre types de contraintes :
 toutes les courses sont assurées, aucune n’est laissée de côté ;
 chaque course est gérée par un véhicule respectant le niveau de confort et les équipements requis ; des substitutions sont parfois autorisées (notion de surclassement) ;
 les enchaînements de courses commerciales doivent être réalisables, c’est-à-dire que le véhicule dispose d’une temps suffisant à la fin d’une course pour se rendre au début de la course suivante ;
 un véhicule retourne en fin de service au dépôt d’où il est parti.

Objectif

L’objectif principal consiste à minimiser le nombre de véhicules utilisés.

Sorties

En sortie, il est attendu un planning des véhicules. Celui-ci spécifie la séquence de courses commerciales, de trajets à vide et de temps d’attente pour chaque véhicule.

Cas d’étude

Nous avons procédé à une étude sur une filiale d’un grand groupe de transport français. Le cas d’étude présentait les caractéristiques suivantes :
 zone géographique : un département ;
 nombre de courses : 921 ;
 taille de la flotte de véhicules : 235 ;
 nombre de catégories de véhicules : 15 ;
 nombre de dépôts : 62, dont 6 centres principaux.

Résultats

Les exploitants utilisaient 220 autocars à l’échelle du département. Nous avons obtenu des solutions avec 212 véhicules, soit une économie de 8 véhicules (-3,6%).

Notre outil permet également de calculer une borne inférieure, c’est-à-dire une valeur en dessous laquelle il n’est pas possible de descendre. Avec les données fournies, cette valeur était de 212. Autrement dit, nous avons prouvé que le nombre de véhicules minimal était atteint.