À l'intérieur des algorithmes de plus en plus complexes qui acheminent les colis jusqu'à votre porte

M. technologie

Si vous deviez remettre 50 colis en main propre, comment feriez-vous pour planifier le meilleur itinéraire ?

C'est un problème théorique avec lequel les mathématiciens et les informaticiens se débattent depuis longtemps, et vous connaissez peut-être même le problème du voyageur de commerce vous-même. En termes simples, il demande : étant donné une liste d'emplacements et les distances entre eux, quel est l'itinéraire le plus court possible qui visite chaque emplacement une fois et revient à l'origine ? De toute évidence, résoudre ce problème est une proposition attrayante pour toute entreprise de commerce électronique qui livre des marchandises, car cela signifie des coûts de carburant inférieurs et moins de chauffeurs.

Mais il y a un hic : le problème devient très dur, très vite. Si un seul conducteur doit se rendre à 57 arrêts, vous avez déjà quattuorvigintillion de combinaisons possibles, explique Marc Kuo, le PDG de la startup d'optimisation d'itinéraire basée à Vancouver. Routifique . C'est un un avec 75 zéros. Les systèmes informatiques existants prendraient des jours ou des semaines pour évaluer tous les itinéraires possibles. Au lieu de rechercher la perfection, les entreprises doivent donc trouver des approches intelligentes pour améliorer autant que possible leurs itinéraires.

Les plus grands acteurs de la livraison ne souhaitent pas parler du sujet. Ni UPS ni DHL n'ont répondu aux demandes d'interviews. FedEx n'a pas pu prévoir de moment pour en parler, même avec un préavis de plus d'une semaine. Et un porte-parole d'Amazon dirait seulement que l'entreprise travaille avec un certain nombre de fournisseurs de services de livraison différents, qui utilisent une technologie haut de gamme pour livrer au nom d'Amazon. Au-delà de cela, il n'avait rien à partager.

Heureusement, certaines petites organisations sont moins méfiantes, alors nous leur avons parlé.

Optimiser les livraisons dans le monde réel est plus épineux que le problème du voyageur de commerce à plusieurs niveaux. Tout d'abord, les distances entre les emplacements doivent être calculées, et comme le savent tous ceux qui ont utilisé Google Maps, il y a toujours plus d'une façon de faire un voyage. Will Salter, directeur général de Parangon , qui fournit des logiciels de routage et de planification dans 60 pays pour des clients tels que le géant britannique des supermarchés Tesco, affirme que les algorithmes de recherche de chemin utilisés dans la planification des livraisons sont hautement personnalisés par rapport à un algorithme Google Maps. Ils tiendront compte des conditions routières, de l'évolution des flux de trafic à différents moments de la journée, et même des avantages marginaux d'un virage à droite à un carrefour.

Ensuite, des centaines de contraintes doivent être prises en compte. Vous pouvez calculer un itinéraire incroyable qui touche toutes vos livraisons, mais pouvez-vous tout mettre à l'arrière de la camionnette ? Combien de temps faudra-t-il pour décharger les aliments surgelés que les aliments de base ? Vaut-il la peine de déposer d'abord des objets lourds pour économiser du carburant ?

Mais James Lohr, responsable des systèmes de planification et de livraison chez Ocado, le plus grand détaillant d'épicerie en ligne au monde (voir The Robotic Grocery Store of the Future Is Here), explique que son système commence par attribuer au hasard les livraisons aux camionnettes pour une certaine zone géographique. , puis calcule combien de temps ces livraisons prendront. Ensuite, il apporte une combinaison de petits et grands changements, allant du changement de l'ordre de deux livraisons au changement de blocs entiers de livraisons entre les véhicules, en évaluant à chaque fois s'il s'agit d'une amélioration. Effectuant quatre millions de mouvements par seconde et gardant une trace des meilleures solutions, il s'approche lentement de l'itinéraire le plus optimal qu'il peut trouver.

Loin du lourd poids informatique de la planification pour les grandes organisations, certaines entreprises développent également des systèmes destinés aux petites entreprises. Kuo de Routific, par exemple, explique que son entreprise espère fournir une puissance de planification d'itinéraire en utilisant des services basés sur le cloud auxquels les conducteurs accèdent via un smartphone. C'est un peu choquant, mais de nombreux conducteurs planifient encore des itinéraires avec un stylo et du papier, dit-il. L'algorithme de son entreprise apporte également des modifications progressives aux itinéraires, mais lorsqu'un petit changement fait une grande différence, l'attention se concentre sur cette baisse pour maximiser l'amélioration, puis l'algorithme passe à autre chose. Routific affirme que son service réduit la longueur des itinéraires de livraison de 40 %.

Il y a de bonnes chances que vous ayez déjà interagi avec ces algorithmes sans vous en rendre compte. Paragon (travaillant pour le compte d'Ikea ​​et du détaillant par catalogue Argos) et Ocado aspirent tous deux les données de leurs analyses lorsqu'ils proposent des fenêtres de livraison aux clients sur leurs sites Web. Il ne propose que des itinéraires qui cadrent bien avec ses plans actuels pour les jours à venir.

C'est une courtoisie envers les conducteurs qui n'a peut-être pas toujours existé. Paragon, Ocado et Routific ont tous rencontré des problèmes culturels lorsqu'il s'agit de convaincre des chauffeurs-livreurs expérimentés que leurs algorithmes savent mieux qu'eux. À un moment donné, si vous alliez à l'endroit où les chauffeurs déjeunaient et disiez que vous étiez un planificateur d'itinéraire, vous auriez peur pour votre vie, dit Ocado's Lohr. J'exagère un peu, bien sûr, mais cela peut être politiquement difficile.

Pendant ce temps, de plus en plus de niveaux de difficulté s'ajoutent au problème d'optimisation lui-même, et il ne semble pas y avoir de fin en vue. Salter de Paragon explique que les clients continuent de demander l'ajout de nouvelles fonctionnalités. Des itinéraires qui minimisent les émissions de dioxyde de carbone. par exemple, sont devenus un favori. Chaque année, nous prenons en compte de plus en plus de contraintes, dit-il. Je ne pense pas qu'il soit possible de vraiment optimiser [les routes] que nous planifions.

cacher