Les mathématiciens accélèrent les bus scolaires

« Le nombre d’élève explose », constate de Michel Chinal, qui dirige l’Ecole internationale de Genève. Le ballet des parents qui amènent et récupèrent leurs enfants crée nombre de problèmes de circulation dans le village de Founex, situé aux portes de Genève. Le service de bus que propose l’Ecole internationale est lent. « Les parents disent souvent qu’ils aimeraient inscrire leur enfant, mais que les trajets sont trop longs. » Les bus assurent le ramassage d’élèves dans la région entre Genève, Morges et la France voisine. Dès lors, comment améliorer les trajets de 11 bus de capacités différentes et qui doivent transporter 283 élèves jusqu’à leur école ? C’est le problème qui a été posé aux mathématiciens de la Chaire d’optimisation discrète.

Parent d’élève, le chimiste Rainer Beck a proposé d’optimiser le service des bus lors des assemblée de parents. Il a demandé à son collègue mathématicien, Friedrich Eisenbrand, de se pencher sur la question. « Trouver un algorithme de calcul simple n’est pas difficile. Mais cette approche n’est pas efficace, car les calculs sont très lents en raison du nombre énorme d’itinéraires possibles. Il fallait donc élaborer un algorithme qui rejette rapidement la plupart des tracés pour que les calculs s’achèvent avant la fin de l’Univers », explique Friedrich Eisenbrand. Aidé de son doctorant, Adrian Bock, le mathématicien a proposé une solution à ce problème complexe. Grâce à quelques astuces, les calculs ne prennent qu’une demi-journée.

Les chercheurs ont modélisé la satisfaction des élèves et de leurs parents à l’aide de paramètres particuliers, par exemple le « regret », un terme utilisé en théorie de la décision. Pour les mathématiciens, le regret est l’écart entre le trajet idéal direct – en voiture – et le tracé du bus. Ce paramètre permet notamment de déterminer le seuil qui décidera plus d’élèves à prendre le bus. Une fois les calculs d’optimisation effectués, le gain est conséquent : les écarts les plus grands entre le trajet du bus et la voiture ont diminué de 25%.

Une collaboration, de multiples applications

L’optimisation est une compétence qui s’exporte au-delà du problème de transport d’écoliers. Les mathématiciens collaborent ainsi avec des leaders mondiaux dans les télécommunications ou l’aviation pour améliorer leurs dispositifs de communication, mais également avec des compagnies d’assurances qui doivent effectuer de longs calculs. Ainsi, dans la vie quotidienne, dès que nous utilisons un réseau, par exemple Internet, un travail d’optimisation se cache derrière.
Au-delà de l’intérêt économique, ces recherches offrent des solutions pour diminuer notre impact sur l’environnement. « Les nuisances de la circulation sont une préoccupation importante de notre école et nous cherchons à trouver des solutions responsables », ajoute Michel Chinal.

Liens :
Théorie du regret et de la décision : http://en.wikipedia.org/wiki/Regret_%28decision_theory%29
Chaire d’optimisation discrète : http://disopt.epfl.ch/
L’Ecole internationale de Genève : http://www.ecolint.ch