Le problème du transport scolaire

Le problème du transport scolaire 

Historique du SBRP 

Le problème du voyageur de commerce (Traveling Sales-man Problem – TSP) est le plus ancien et le plus connu des problèmes dans la recherche opérationnelle, étudié depuis le 1ge siècle par William Rowan Hamilton. Ce dernier a tenté de répondre à une problématique rencontrée par un vendeur qui devait visiter une série de villes une seule fois et revenir à son point de départ en parcourant la trajectoire la plus courte (Ghiani, 2000). C’ est un problème NP difficile, car trouver l’ordre pour des villes à visiter quand il s’agit de 5 villes est synonyme de trouver le chemin le plus court entre 120 possibilités. Par contre, lorsqu’on double le nombre de villes Cl 0), ce sont plutôt 3 628 800 chemins possibles qu’on retrouve (Newton et Thomas, 1969).

Le problème de tournées de véhicules (Vehicle Routing Problem – VRP) est un dérivé du TSP. Il s’agit d’une flotte de véhicules localisée à un point de départ, où on doit visiter un certain nombre de clients pour la livraison d’objets, afin de minimiser la distance totale. Le VRP introduit la notion de la capacité de la flotte à ne pas dépasser, qui peut être homogène ou hétérogène, et la quantité de la demande des clients à satisfaire. Chaque tournée de véhicule de la flotte doit débuter et finir au point de départ (Carie et al., 2007).

Plusieurs variantes se sont développées à partir du VRP, par l’ajout ou la combinaison de contraintes. On trouve par exemple le problème de tournées de véhicules avec fenêtre de temps (Vehicle Routing Problem with Time Window- VRPTW), où le client doit être servi à l’intérieur d’un intervalle de temps (Desrochets et al. 1992). On retrouve aussi le problème de tournées de véhicules multi points de chute (Multi-Depot Vehicle Routing Problem – MD VRP), où les clients doivent être affectés à un point et servis par l’un des véhicules basés dans les alentours (Montoya-Torres et al., 2015). On retrouve le problème de tournées de véhicules avec la combinaison de la gestion des points d’embarquement, de débarquements et la fenêtre de temps (Vehicle Routing Problem with Simulation Pickup and Delivery and Time Window – VRSPDTW). Ce genre de problème combine la contrainte de la fenêtre du temps et celle de l’emplacement des entrepôts (Wang et al., 2015). Puis, le problème du transport scolaire (School Bus Routing Problem – SBRP) vise la planification des tournées d’une flotte d’ autobus scolaires, où chaque autobus doit ramasser des élèves de différents arrêts pour les transporter vers leur école. Le tout doit respecter la durée du voyage maximal d’un élève, la capacité maximale d’ un autobus et la fenêtre de temps pour l’embarquement et le débarquement (Martinez et al. 2010). Rashidi et al. (2009) précisent que le problème du SBRP est une variante du problème des tournées de véhicules avec capacité dans lequel les élèves sont regroupés puis affectés à des arrêts. Le véhicule doit visiter une seule fois les arrêts, et le circuit ne prend fin que quand tous les élèves sont transportés (Rashidi et al., 2009).

Recherches antérieures sur le SBRP 

Les approches utilisées diffèrent beaucoup d’un auteur à l’ autre. Que ce soit au niveau des contraintes considérées, de l’objectif visé, de la taille de l’échantillon, de l’algorithm,e utilisé, ou de l’étape du SBRP considérée. En 1969, Newton et Thomas proposaient une méthode pour générer des parcours d’autobus scolaires et des horaires par ordinateur. Ils ont d’ abord proposé une formulation en nombres entiers. Avec seulement 20 origines et 100 arrêts à visiter, ils ont identifié 213840 variables et 40*(98 !) contraintes (Newton et Thomas, 1969).

Dû au temps de calcul trop élevé, il était nécessaire de trouver d’ autres méthodes de résolution. La procédure proposée par l’auteur est basée sur deux étapes, soit l’utilisation d’une heuristique du voisin le plus proche pour créer des routes et l’utilisation d’un algorithme A, qui effectue des itérations sur la solution initiale pour l’améliorer. À chaque itération, un contrôle des contraintes, comme la capacité des autobus et le délai maximal du voyage, est fait. Une des limites de cette méthode est la capacité des autobus qui est supposée homogène et les routes qui sont créées par école, c’est-à-dire que l’autobus ne ramasse que les élèves de la même école, plus communément appelé charge unique.

Li et Fu (2002) soulignent qu’il n’y a pas d’approche unique pour l’étude du SBRP et ajoutent que les méthodes de résolution dépendent du contexte du problème. Park et al. (2010) présentent deux stratégies qui reviennent à plusieurs reprises dans les écrits. La première stratégie est le LAR (Location Allocation Routing), qui consiste à sélectionner des arrêts (location), puis à affecter les élèves aux arrêts (allocation). Ensuite, on regroupe les arrêts pour créer des routes et parcours (routing). Cette stratégie était choisie par Bodin et Berman (1979), Dulac et al. (1980) et Desrosiers et al. (1984). La deuxième stratégie, l’ARL (Allocation Routing Location), consiste à constituer des groupes géographiques, où chaque regroupement contient un nombre d’ élèves qui correspond à la capacité des autobus (allocation). On sélectionne par la suite des arrêts pour créer des routes (routing), et enfin, on affecte les élèves aux arrêts (location). Ledesma et al. (2013) et Kinable et al.(2013) ont utilisé la méthode ARL. Par contre, selon la même source, la méthode LAR a tendance de créer plus de routes, car elle ne tient pas compte de l’ effet de la répartition des élèves par rapport à la capacité des autobus.

Park et Kim (2010) proposent une stratégie en cinq étapes, soit la préparation des données, la sélection des arrêts d’autobus, la génération des parcours par le regroupement des arrêts, le réglage de la plage des temps des écoles et l’ordonnancement des autobus. Selon ces auteurs, peu de chercheurs se sont intéressés à la sélection des arrêts. La caractéristique du type de la charge est aussi une caractéristique importante présente dans la littérature liée au SBRP. Elle peut être simple, c’est-à-dire qu ‘on ne transporte, dans le même autobus que les élèves de la même école, ou bien mixte, qui signifie qu’on peut accepter le transport des élèves de plusieurs écoles en même temps. Cette dernière fut introduite et étudiée par Bodin et Berman (1979). Braca et al. (1997) furent les précurseurs qui ont développé une approche informatique pour la charge mixte par la proposition d’ une heuristique modifiée. Leur problème comprend la capacité, la distance et la fenêtre de temps pour les écoles, la contrainte de temps maximal du voyage et, pour la première fois dans les SBRP deux contraintes furent ajoutées, soit le nombre minimal d’élèves par voyage et une heure minimal de visite (par exemple pas avant 7hOO).