Trois problèmes de transport à optimiser

Comment transporter des matières premières de la façon la moins coûteuse possible, en temps ou en énergie ? C’est la question centrale d’un domaine des mathématiques peu connu, le « transport optimal ». Partons à sa découverte à travers quelques exemples.

Barge à charbon© LPLT / Wikimedia Commons

Au XVIIIe siècle, le mathématicien Gaspard Monge conçoit un problème bien retors. En un endroit un tas de sable qui doit servir à boucher un trou en un autre endroit. Il faut décider pour chaque pelletée de sable, de l’endroit où la verser, de manière à ce que l’effort requis pour boucher la totalité du trou soit le plus faible possible. Ainsi, vaut-il mieux d’abord combler la partie du trou la plus éloignée du tas de sable, ou au contraire la plus proche ?

Comment répartir la production ?
Ce problème d’optimisation se retrouve dans de nombreux contextes. Imaginez une région où sont disséminées des mines de charbon plus ou moins grosses et des aciéries nécessitant du charbon en plus ou moins grande quantité pour fonctionner. Comment répartir la production de chaque mine entre les différentes aciéries, afin de minimiser les coûts de transport, proportionnels à la distance à parcourir ? Le cadre mathématique du tas de sable et du trou à combler décrit aussi l’association mine-aciérie avec la même question : existe-t-il une solution optimale pour minimiser le coût de transport ou  maximiser la productivité du service ?

Transport branché
Imaginons à présent que le coût du transport du charbon entre la mine et l’aciérie est proportionnel à la longueur, mais de moins en moins coûteux (en proportion) quand la masse transportée augmente. On a alors intérêt à mettre en place à côté d’un groupe de mines un centre de collecte, et à expédier depuis ce centre tout le charbon rassemblé jusqu’à un centre de répartition qui va irriguer plusieurs aciéries dans son voisinage immédiat. Le réseau ainsi formé est un « transport branché ». À l’inverse, certains réseaux ont un coût de transport de plus en plus élevé avec leur fréquentation : ainsi, le temps de transport sur les réseaux routiers s’allonge quand de plus en plus d’automobiles
les empruntent. Pour ce « transport congestionné », on étudie la situation d’équilibre où tous les automobilistes sont satisfaits de leur itinéraire, le « meilleur » étant donnée la situation du réseau. Ces problèmes de transport et d’optimisation s’avèrent de redoutables casse-tête mathématiques. Il aura fallu attendre plus de deux siècles pour montrer que le problème de Monge pouvait toujours être résolu… Rien d’étonnant que des versions plus élaborées continuent à exciter la sagacité des mathématiciens d’Orsay !


Fig. 1
: Le transport branché permet de mettre en place des centres de collecte et de répartition lorsque le coût dépend à la fois de la distance parcourue et de la quantité de matière transportée.

© F. Santambrogio , Laboratoire de Mathématiques d’Orsay


Fig. 2
: Comment attribuer la production de chaque mine (en orange) à une usine (en violet) avec aussi peu de transport que possible ? Il faut déjà éviter les croisements inutiles….


CONTACT

Fillipo Santambrogio, Laboratoire de Mathématiques d’Orsay, filippo.santambrogio@math.u-psud.fr