Transport de marchandises - Mille milliards de milliards de solutions

L’économie repose en partie sur la distribution efficace des produits vers leurs lieux d’entreposage ou de consommation. La livraison se fait vers les magasins, les bureaux, les entreprises, les résidences. Ces déplacements accaparent en moyenne à peu près le tiers des ressources des compagnies. Certaines recherches montrent que l’optimisation des systèmes de transport peut faire économiser jusqu’à 20 % des frais.
Photo: Agence France-Presse (photo) Saul Loeb L’économie repose en partie sur la distribution efficace des produits vers leurs lieux d’entreposage ou de consommation. La livraison se fait vers les magasins, les bureaux, les entreprises, les résidences. Ces déplacements accaparent en moyenne à peu près le tiers des ressources des compagnies. Certaines recherches montrent que l’optimisation des systèmes de transport peut faire économiser jusqu’à 20 % des frais.

Le problème du voyageur de commerce occupe les mathématiciens et les ingénieurs depuis des décennies. Une tournée de 30 villes, par exemple, offre au voyageur plus de possibilités de parcours qu’il y a d’atomes dans l’univers. Montréal est la capitale mondiale des recherches opérationnelles dans ce domaine. Et un jeune diplômé de l’École polytechnique vient de mettre au point une nouvelle méthode révolutionnaire pour trouver rapidement des solutions efficaces.
 

 

Des minidrones pour livrer des paquets, un à la fois, à la porte de chacun des clients. Amazon a dévoilé il y a quelques jours cet incroyable projet, et tous les médias du monde sont tombés dans le panneau, y compris ici. Les sceptiques ont vite exposé les immenses problèmes logistiques et juridiques posés par l’idée de cette « vaste plaisanterie ».

 

Et si la championne de la vente en ligne avait tout simplement trouvé le filon pour faire parler d’elle, partout et gratuitement, la veille du Cyber Monday, jour de la course folle aux « webaubaines » ? Et si Amazon cherchait à faire paravent aux reportages récents sur les déplorables conditions de travail de ses employés, y compris la surveillance continue des salariés par des systèmes de haute technologie ?

 

Dans la vraie de vraie vie, ici comme ailleurs, hier comme demain, les livreurs continuent donc de porter les paquets en cherchant le parcours le plus court possible. Pour un seul point de chute, avec ou sans drone, en gros, il n’y a qu’à choisir la ligne la plus droite ou la voie la plus rapide. Pour deux clients, la solution reste assez simple. Tout baigne.

 

Pour six livraisons, le casse-tête se complexifie jusqu’à 720 routes possibles. Pour vingt maisons ou villes, il existe plus de 100 billiards de routes (100 suivi de 15 zéros). Rendu à 33 points de chute, les options dépassent l’entendement. Dans ce cas, pour calculer toutes les routes envisageables afin de déterminer celle optimale, il faudrait 28 trillions d’années à plus de 100 000 ordinateurs travaillant de concert. Aussi bien dire l’éternité.

 

Il y a la théorie. Il y a la pratique. Dans les faits, les voyageurs peuvent très bien et très facilement se rendre chez une trentaine de clients quitte à couper les coins ronds en repassant quelques fois au même endroit.

 

La compagnie Procter Gamble a d’ailleurs lancé en 1962 un concours mondial pour résoudre ce problème concret envisageant 32 villes à visiter par un seul voyageur de commerce. Le tracé à la main du mathématicien qui avait remporté le gros lot de 10 000 $ était le plus court de ceux de tous les participants, mais pas nécessairement le plus court possible.

 

La métropole et son prophète

 

Dans In Pursuit of the Travelling Salesman, le mathématicien William J. Cook a présenté ce problème du voyageur de commerce comme « le point de mire d’un débat élargi sur la nature de la complexité et les limites envisageables de la connaissance humaine ».

 

Or ce « point de mire » vise nécessairement Montréal, considérée comme la capitale mondiale de cette recherche opérationnelle sur la tournée de véhicules qui occupe des cerveaux bien formés depuis des décennies. Et si la Mecque de cette discipline est ici, le jeune chercheur Thibaut Vidal est maintenant son prophète.

 

C’est le professeur de l’École polytechnique Michel Gendreau qui le dit, lui-même une sommité internationale dans le domaine. « Thibaut Vidal a défini une méthode hybride unifiée pour les tournées, annonçait-il la veille de la collation des grades, au printemps dernier. Il a inventé une sorte de couteau suisse de notre secteur. Il a découvert le Graal. »

 

Le compliment fait rigoler le nouveau docteur, qui a officiellement reçu son titre de l’Université de Montréal en juin.

 

« Polytechnique est une école reconnue mondialement et mon couteau suisse, comme le présente le professeur Gendreau, est le résultat de tout un historique », dit le jeune chercheur d’origine française, joint au prestigieux Massachusetts Institute of Technology (MIT) de Boston où il poursuit ses études postdoctorales.

 

Il explique que le problème du voyageur de commerce et ses variantes sont abordés par à peu près 2000 articles publiés depuis six décennies. Or les trois plus importants savants de cette manne sont montréalais : les professeurs Gilbert Laporte (qui a publié une soixantaine d’articles), Jean-Yves Potevin et M. Gendreau lui-même (avec une quarantaine de textes chacun).

 

« Ce problème du commis voyageur, celui du concours de Procter Gamble, on sait assez bien le résoudre maintenant, alors on s’intéresse à des variantes plus complexes, dit le chercheur. Au lieu de faire juste une tournée, par exemple, le véhicule doit en faire plusieurs. Ou bien plusieurs véhicules travaillent ensemble pour satisfaire plusieurs centaines de clients la même journée en partant d’un même dépôt. Il y a plus de solutions que d’atomes dans l’univers. »

 

Renaissance d’un commis voyageur

 

L’économie repose en partie sur la distribution efficace des produits vers leurs lieux d’entreposage ou de consommation. La livraison se fait vers les magasins, les bureaux, les entreprises, les résidences. Ces déplacements accaparent en moyenne à peu près le tiers des ressources des compagnies. Certaines recherches montrent que l’optimisation des systèmes de transport peut faire économiser jusqu’à 20 % des frais.

 

Ces problèmes d’optimisation combinatoires se révèlent immensément complexes. Une étude française de l’Agence de l’environnement et de la maîtrise de l’énergie a par exemple démontré qu’en ville, mieux vaut utiliser un plus gros camion au lieu de multiplier les déplacements d’une flotte de plus petits véhicules.

 

Ainsi, douze fourgons de livraison de 500 kg chacun effectuant des déplacements parallèles vers douze magasins situés à 10 km du centre de distribution consomment plus d’énergie et font plus de bruit qu’un seul grand porteur de six tonnes effectuant une seule tournée auprès de la douzaine de clients à partir du même centre.

 

Encore faut-il savoir orienter le mastodonte. Depuis vingt ans, les chercheurs se concentraient sur ces variantes, jusqu’à multiplier les études liées à des nécessités pratiques. Par exemple, la volonté de livrer à telle heure, de prendre en compte l’inventaire ou la congestion routière.

 

« Cette démarche a multiplié les problèmes, résume M. Vidal. On n’étudiait plus un problème théorique mais des dizaines de cas. Chacun travaillait dans son coin, avec sa méthode. Alors moi, je suis intervenu en reprenant tous ces problèmes pour en quelque sorte les réunifier, montrer qu’ils avaient une structure commune, qu’ils étaient tous bâtis sur le même modèle. J’ai donc proposé une méthode unique qui les résout tous. »

 

Les méthodes génétiques

 

Cette méthode assimilée au Graal est développée dans le doctorat intitulé Approches générales de résolution pour les problèmes multi-attributs de tournées de véhicules et confection d’horaire. Le chercheur explique que son idée, « pas si compliquée en fait »,s’inspire des méthodes dites génétiques qui imitent l’évolution des espèces.

 

« Imaginons que nous trouvons une dizaine de solutions, une dizaine de parcours différents, certains un peu plus longs, d’autres plus courts, dit-il. Ma proposition, c’est tout simplement de les croiser ensemble, comme on le fait en génétique.

 

« En prenant un bout de l’un et un bout de l’autre, en recollant ces segments, en améliorant le résultat avec des choix évidents, par exemple en liant deux points rapprochés, on génère un nouvel individu, une nouvelle solution qu’on réinjecte dans le système.

 

« À la longue, on conserve les meilleures. En effectuant ce processus des milliers et des millions de fois, on aboutit à des solutions qui sont de mieux en mieux. Au final, on se retrouve avec une version quasiment optimale au problème. »

 

Cette méthode très pratique va très vite avec l’ordinateur, qui permet de rejeter rapidement les solutions les moins efficaces. « Surtout, ce n’est pas fréquent pour l’esprit humain de croiser deux solutions, et encore moins cent, remarque M. Vidal. En général, on a plutôt tendance à en choisir une seule, puis à l’améliorer. Évidemment, ce croisement est rendu possible par les ordinateurs et les algorithmes qui permettent de tester des millions d’essais. »

 

La méthode Vidal s’avère encore plus riche d’un point de vue heuristique. Elle ne fait pas que considérer plusieurs solutions : dans les faits, elle élimine les propositions les moins performantes par grappes, en paquets.

 

« La méthode génétique existe depuis quelques années. L’une des innovations de mon travail a consisté à modifier un peu le concept de fonction objectif qui sert de critère pour juger de la meilleure solution. Ma méthode n’élimine pas seulement les mauvaises solutions en ce qui concerne la distance, par exemple, mais aussi celles qui sont mauvaises en matière de diversité, celles qui sont trop proches des autres, quoi. Par ce moyen, on arrive à mieux préserver la différence et à converger vers de meilleurs résultats. »

 

Surtout, c’est simple, et ça marche. La méthode résout certains cas en quelques minutes à peine, là où des équipes de spécialistes planchaient autrefois des jours et des jours. « Et, en général, on fait beaucoup mieux », dit M. Vidal, qui avait déjà expérimenté son couteau suisse sur une trentaine de problèmes au moment de l’interview.

 

Par exemple, il a testé l’affaire sur une tournée de véhicule tenant compte des heures de congestion du réseau routier, des horaires de livraison changeants, des volumes complexes de colis, etc.

 

Taxis, ambulances, secours

 

Sa méthode s’applique aussi bien aux flottes de taxis qu’aux positionnements stratégiques des ambulances dans une ville. Aussi bien à la livraison des secours humanitaires après une catastrophe qu’à la tournée d’inspection de puits de pétrole. Et au problème classique du voyageur de commerce de Procter Gamble, évidemment.

 

« Dans mon métier, on formule un problème et on le résout, résume le jeune savant. Et puis on recommence avec un nouveau cas. »

À voir en vidéo