Ce texte est survenu en raison du plaisir du café aléatoire dans Yandex - le système prend rendez-vous pour deux employés au hasard s'ils indiquent qu'ils souhaitent participer à de telles réunions. Mes interlocuteurs ont trouvé intéressante l'histoire de ce que je faisais, et maintenant j'ai mis la main sur l'offrir à un public plus large.Avant Habr, j'ai donné une conférence à la Faculté d'Informatique de HSE et Yandex - j'ai dit aux étudiants du FCS exactement la même chose, dont je vais vous parler maintenant (à la fin du post il y a une vidéo) À savoir, comment voyager avec des chauffeurs livrant des commandes dans des magasins en ligne a convaincu notre équipe de proposer un nouveau service sur la logistique. J'espère que je pourrai vous transmettre mes sentiments de cette région: je me suis rendu aux Gazelles et à Largus, j'ai écouté les plaintes des employés au sujet de la difficile «tante de Noginsk» et j'ai vu comment une commande de trois scooters pour trois enfants s'est transformée en drame. . Et à la fin, parlons de la technologie.Partie 1. Comment tout a commencé
Il y a quelques années, en me promenant dans le bureau en me demandant s'il était temps pour moi de changer quelque chose dans ma vie, je suis tombé presque accidentellement dans un couloir avec un collègue que je respectais beaucoup sur l'un de mes projets passés. Il s'est avéré qu'il est passé à une startup interne, et ils sont juste à la recherche d'un analyste. Je me suis donc retrouvé dans une division appelée B2BGeo. À l'époque, ce petit groupe était censé faire quelque chose pour les entreprises basées sur les géoservices Yandex - mais personne ne savait lequel. Historiquement, les employés des géoservices ont créé des applications mobiles de bureau Yandex.Maps, Maps, Navigator et Metro. De plus, cette unité comprend une infrastructure impressionnante: développement d'un moteur de routage, d'un service de carte, reconnaissance des panneaux routiers, extraction de données à partir d'images satellites, et bien plus encore. Les cartes Web et Yandex.Navigator sont des applications,destiné à l'utilisateur de masse. Parmi les services pour les entreprises, nous n'avions qu'un ensemble d'API de cartographie: un widget de carte JS pour les sites, MapKit pour les applications et une API de construction de routes REST.L'équipe B2BGeo, avant de commencer à vendre des produits pour les entreprises, a donc dû proposer ces produits. Nous avons passé un peu de temps sur les études de marché et le prototypage. Les prototypes étaient intéressants, par exemple, une carte de la qualité d'un signal cellulaire à l'intérieur des bâtiments. Ensuite, les opérateurs de téléphonie cellulaire n'ont pas utilisé les énormes quantités de données dont ils disposent, mesurant la qualité principalement dans les rues et de manière plutôt primitive. Un autre exemple de prototype est un routeur universel personnalisable avec apprentissage automatique. Soit dit en passant, ci-après appelé routeur et routeur n'est pas un équipement réseau, mais un programme de création d'itinéraire.Certains prototypes n'ont pas décollé, d'autres ne seraient pas intéressés par un nombre suffisant d'entreprises. Il fallait quelque chose de plus grand. À l'avenir, il fera tourner le monde et ouvrira de nouveaux horizons et, pour commencer, il apportera des avantages considérables grâce aux géotechnologies. Nous avons eu une séance stratégique: nous avons quitté le bureau et réfléchi pendant deux jours. Sur la base des résultats de la session, nous avons identifié une industrie où les perspectives sont suffisantes pour nous. Notre choix s'est porté sur la logistique.En Russie, beaucoup de véhicules commerciaux, de nombreuses sociétés de transport et de messagerie transportent quelque chose quelque part. Et tous, très probablement, effectuent leurs itinéraires manuellement ou à l'aide de programmes qui ne fonctionnent probablement pas très bien, car ils ne prennent pas en compte les embouteillages. Et derrière nous, il y avait tout un Yandex avec beaucoup de matériel, seul un petit nombre d'entreprises (seulement un exemple rare - Google) avait des exemples de données et de bons programmeurs. Les compétences dans ce domaine sont rares et précieuses: Uber a à un moment donné racheté toute une équipe cartographique.Encouragés par cette perspective, nous avons convenu avec l'un des agrégateurs de livraison (une entreprise qui distribue les commandes de divers magasins en ligne) afin qu'ils nous laissent regarder leur travail de l'intérieur vers l'extérieur, «s'immerger dans l'industrie». Les membres de notre petite équipe ont voyagé avec des courriers livrant les commandes et se sont assis à côté du logisticien qui planifie les itinéraires.Partie 2. Immersion dans l'industrie
8 h, une des zones industrielles derrière le troisième périphérique, où se trouvent l'entrepôt et le bureau de l'agrégateur. Une petite pièce, qui rappelle la poste: le coin est clôturé avec un bureau, à l'intérieur - ordinateurs logistiques, téléphones, imprimantes. Chaises grasses et chaises d'ordinateur avec dermantine craquelée. Une boîte avec des téléphones chinois bon marché, un papier avec un numéro est collé sur chacun - ils sont remis aux conducteurs. Il y a de simples canapés-banquets le long des murs, un stand avec des imprimés à la sortie: règles de transport, une sorte d'instructions internes, un tableau des amendes - par exemple, 200-300 roubles seront pris au chauffeur pour une commande non livrée. L'agrégateur a également un bureau normal, où le directeur, les gestionnaires et la comptabilité sont assis à de belles tables, mais les événements clés pour nous se produisent dans cette petite salle.
Les conducteurs fument à l'extérieur, mais il fait frais là-bas, la plupart sont à l'intérieur, donc c'est bondé et étouffant dans la pièce. Mat-remat sur trois étages, très sombre le matin, quelqu'un veut récupérer son paquet de factures et le laisser charger, quelqu'un a un accroc, il est mécontent. La situation est tendue, il y a deux logisticiens, et ils sont au savon. On nous dit que c'est une journée normale, juste le matin, en partant pour les itinéraires, il y a toujours un parc. La nuit, quand les préparatifs se sont déroulés, il y a eu aussi une noyade, quelque part dans une heure la tension va diminuer, et le logisticien pourra se reposer.Plusieurs chauffeurs sont informés que Yandex vous accompagnera. Ils sont surpris et pas particulièrement satisfaits - on ne sait pas pourquoi ils sont si heureux et s'ils nous ont incités à les suivre. Nous, les employés de bureau , les informaticiens avec des sacs à dos, sommes en contraste frappant avec ces hommes sombres.J'ai la Gazelle, elle a un chauffeur et un transitaire, je m'assois troisième avec un sac à dos dans les bras et essaie de ne pas prendre trop de place. Les commandes sont déjà chargées dans le corps, nous commençons.
Plus tard, j'ai appris que précédait généralement le départ des voitures sur l'itinéraire.Supposons qu'aujourd'hui soit mercredi, vous commandez un réfrigérateur sur un petit site que vous avez trouvé sur Yandex.Market, ce magasin a le meilleur prix et des critiques raisonnables. La livraison n'est possible que le vendredi, elle vous convient. Le site n'est vraiment qu'une vitrine; pour les très petits sites, le responsable qui a confirmé la commande peut généralement être le seul employé. Votre réfrigérateur est situé quelque part dans un entrepôt près de Podolsk avec d'autres réfrigérateurs de la même entreprise (un petit magasin n'a pas son propre entrepôt - en fait, la vente provient de l'entrepôt du fabricant). Le gestionnaire réserve ce réfrigérateur et envoie la commande à l'agrégateur de livraison. Mercredi, l'agrégateur collecte les commandes et envoie jeudi un gros camion à Podolsk pour vos réfrigérateurs et d'autres commandés dans d'autres magasins.Tout cela vient de l'entrepôt loué par l'agrégateur dans la zone industrielle de Moscou.Le jeudi soir, lorsque toutes les marchandises à livrer le vendredi sont collectées à l'entrepôt, les logisticiens s'assoient pour le travail. À 4-5 heures du matin, ils doivent distribuer les commandes par machine, les employés de l'entrepôt mettent les marchandises en tas, chaque machine a son propre tas - vous devez leur laisser une marge de temps pour ce travail. Un tas sera chargé dans la voiture et il plaira aux clients.
Pour répartir les commandes par machine, le logisticien utilise un programme spécialement acheté. Il s'intègre à 1C: Enterprise, les données sur les machines (poids et volume de chargement autorisés, coût d'une journée de travail) et sur les marchandises (poids, volume, adresse et intervalle de livraison, contacts clients, commentaires) y sont chargées. Certaines voitures appartiennent à l'agrégateur, celle-ci avait des talons (Lada Largus) et des Gazelles (Gazelle / Ford Transit / Hyundai Porter). Il y avait aussi des courriers loués sur des véhicules personnels, généralement sur des familiales (nous avons vu Ford Focus, Mitsubishi Pajero et même quelques vieilles Lexus).Le programme a été écrit par de bons programmeurs, il sait comment répartir les charges sur les voitures et construire la route optimale (par temps ou kilométrage) pour éviter les commandes, étant donné un tas de paramètres. Mais le logisticien n'utilise en aucune façon cette fonctionnalité. Mais il utilise activement la visualisation des commandes sur la carte. Le programme vous permet de dessiner des zones de polygones sur la carte et d'afficher des statistiques sur le fret et les itinéraires à l'intérieur de ces zones. Les logisticiens ont divisé tout Moscou et la région de Moscou jusqu'au Big Concrete (autoroute A108) en zones approximativement du type suivant:
Au centre, il y a quelques petites zones, puis des secteurs radiaux commencent qui longent les principales autoroutes et englobent la région.Dans chacune de ces zones, certains conducteurs travaillent, qui la connaissent généralement, connaissent les routes, les caractéristiques de la circulation, savent où se trouvent les agents de la circulation, quelles sont les restrictions et les panneaux pour les camions. Le logisticien, quant à lui, sait combien de commandes l'équipage peut transporter. Il donne plus d'expérience sous 30 commandes, et pour ceux qui ont commencé à travailler récemment, 20-25 commandes. Il regarde combien il y a de commandes dans une certaine zone, et s'il y en a trop, il les jette dans la suivante. Ou ajoute un voisin: disons, le logisticien est ami avec certains chauffeurs et leur donne des ordres «légers», qui sont susceptibles d'être en route. Et le conducteur mal aimé peut ennuyer. Par exemple, lancer une commande pour un client, dont on sait à l'avance qu'il est pointilleux, nécessitera une livraison strictement à l'heure indiquée, imprimera toutes les marchandises, les examinera pendant longtemps. Outre,le logisticien peut simplement donner moins de commandes au conducteur: pour chaque commande, le conducteur reçoit 200 roubles, il est intéressé à en avoir plus.La possibilité de planifier des itinéraires dans le programme est complètement ignorée. Cette possibilité n'a pas de sens dans un tel système: si le logisticien indique au chauffeur comment il doit contourner les commandes, le chauffeur lui répondra: "Vous êtes assis dans le bureau là-bas, et je suis dans cette zone comme le dos de ma main". Ainsi, le logisticien n'assigne que les commandes de la voiture, la tâche du chauffeur est formulée comme une pile dans l'entrepôt et une pile de factures imprimées.Revenons donc à la Gazelle. Notre région est l'autoroute des passionnés et plus loin vers Noginsk, il y aura environ 15 commandes pour le périphérique de Moscou, j'y irai. Le chauffeur part pour le troisième anneau de transport, date à laquelle le transitaire prend un paquet de factures et les transfère dans le bon ordre. L'ordre correct est le suivant:- Nous allons tout d'abord longer l'autoroute des passionnés en direction du périphérique de Moscou et prendre toutes les commandes à droite. On ne le prend pas toujours à gauche, il peut y avoir des embouteillages en traversant l'autoroute, mieux vaut les prendre le soir. Ensuite, nous partirons pour la région, nous l'emmènerons là-bas. Le soir, nous rentrerons et porterons le reste.- Mais, par exemple, le premier ordre dans la pile - avec le souhait «après 14 heures»? Le laisser pour la soirée?- C'est possible pour la soirée, mais il vaut mieux essayer d'accepter de le donner maintenant.Le processus de négociation a été immédiatement démontré. À 9h30, le transitaire a appelé la commande téléphonique après 14 heures:- Bonjour, livraison, nous sommes déjà dans votre région, pouvez-vous accepter la commande? .. Nous irons dans la région après votre région, et nous ne reviendrons pas ici avant le soir. Peut-être que nous reviendrons après neuf heures, ou peut-être que nous resterons complètement dans la région, c'est une entreprise imprévisible, nous devrons peut-être reporter la livraison le lendemain ... Eh bien, nous arriverons dans 15 minutes.C’est alors que j’ai réalisé d’où venaient les coursiers qui disaient: "Bonjour, je suis déjà avec vous!" - et ignorez complètement mes commentaires et mon délai de livraison!Des collègues qui ont conduit dans d'autres voitures m'ont dit que quelqu'un avait un chauffeur ou un transitaire qui a honnêtement appelé le client une heure avant la livraison. Les miens n'étaient pas très sociables, ils ont appelé pendant une quinzaine de minutes, ont prononcé à haute voix les commentaires des clients. De simples souhaits («n'appelez pas l'interphone, l'enfant dort») ont été pris en compte, mais tout ce qui a influencé l'itinéraire a été généralement ignoré. En changeant les factures, le transitaire a pêché une commande qui devait être acheminée dans un village à quelques kilomètres de Noginsk.- Oh, encore cette tante. Rappelez-vous, elle avait une commande, puis un retour sur mariage? Maintenant une nouvelle commande.- Ouais, relevez la machine à laver. Un autre est intéressant: «veuillez livrer du 12 au 16». Comment l'imagine-t-elle?- Oui, en général, ils ne comprennent pas ce qu'ils écrivent.Je pense que oui: si vous commandez une machine à laver à Noginsk, alors asseyez-vous et attendez calmement qu'elle soit apportée. Soit en quelque sorte d'accord avec les voisins, soit prenez un congé. Nous ne pouvons pas aller la voir tous les jours à Noginsk.Je suis descendu près de la rocade de Moscou et le chauffeur a emmené la Gazelle plus loin le long de l'autoroute Gorki. En fait, ce ne sont pas des méchants, et malgré le bourdonnement contre les clients (cela représentait au moins les deux tiers de toutes les conversations), ils auraient probablement réussi à livrer la laveuse à 16 ans.Mon deuxième voyage a eu lieu dans une voiture plus petite: la cargaison Largus a roulé dans le district administratif du Nord-Ouest. La cargaison était petite, pas de réfrigérateur, donc le chauffeur était seul. Oncle est devenu sociable, nous avons beaucoup parlé de lui. Il a dit qu'en général, il est un maître des sports de lutte, travaille comme entraîneur, mais maintenant tout est sourd, alors il se met au clair de lune comme coursier. L'argent est petit, mais l'augmentation est agréable: environ 2 000 sont obtenus par jour. Il est facile de livrer des commandes, il fonctionne quand il veut. Bien sûr, il y a des nuances: vous rencontrez des clients désagréables, vous devez manger des sandwichs stockés dans la voiture, vous êtes pressé, vous n'allez même pas aux toilettes, vous devez demander aux clients. Mais dans l'ensemble, il est assez prospère, pour lui c'est plutôt du divertissement.C'est drôle: des collègues, en particulier des filles, des employés des services de livraison ont également raconté des histoires que «le courrier n'est pas le travail principal, mais uniquement pour l'âme», «en général, je vais généralement dans un behhe», etc.Je me souviens que dans le domaine de Rublevka ou Krylatsky une telle conversation:- Une fois dans la ville, il a apporté un ordre, là, ils ont des appartements dans un gratte-ciel, les couloirs sont tous en marbre, je vais dans l'appartement - tapis, peintures dans des cadres dorés, quelques manteaux de fourrure accrochés, qui n'est tout simplement pas là. Une commande pour 5800, alors il a demandé un changement de 200 roubles, comptez?!- Alors, peut-être qu'il a des manteaux de fourrure et des peintures précisément parce qu'il économise même 200 roubles.Après mes paroles, le chauffeur réfléchit longuement. Et une heure plus tard, nous sommes arrivés à Schukino et j'ai «tout compris» de cette entreprise.Dans le stylo suivant, on a noté que tout n'était pas en ordre avec la commande: sur trois scooters pour enfants achetés d'une valeur totale de 20 mille roubles, seuls deux étaient dans la voiture. Le chauffeur a appelé le logisticien. Il s'est avéré que la femme avait commandé trois scooters lundi, mais hier, mercredi, le troisième scooter a été placé par erreur dans la mauvaise voiture. Et c'était une voiture privée, pour une raison quelconque, il n'est pas retourné à l'entrepôt le soir, comme le font les conducteurs "réguliers", et le scooter continue de rouler avec. On pourrait essayer de l'intercepter, mais aujourd'hui il vaquer à ses occupations, il est impossible de le traverser. La prochaine fois, il travaillera demain (vendredi), mais ce n'est pas exact. Il est garanti de réunir les trois scooters et de les prendre en même temps ne sera possible que samedi.Armé de ces informations, le chauffeur a appelé le client. Il y avait une femme très mécontente. Elle a déclaré: samedi à 10 heures, ils ont des vacances en famille, où ils voulaient donner des scooters à ses trois enfants. Par conséquent, elle en a strictement besoin au montant de trois pièces, elle n'accepte pas un remboursement partiel et ne comprend pas du tout comment cela est possible - elle a passé la commande lundi, et maintenant nous, le magasin de scooters, la lui substituons. La livraison le samedi à une heure indéterminée ne lui convient pas catégoriquement. Demain, elle est à la maison avant le dîner, si vous ne pouvez pas aujourd'hui ou demain matin, elle annule la commande et maudit le magasin au troisième genou (et vous pouvez le comprendre).Partie 3. Minimum local
Le magasin achète un service de livraison de commandes auprès d'une entreprise de messagerie. Pour les scooters non livrés, il infligera une amende à une entreprise de messagerie pour 500 roubles. La société infligera une amende de 200 à 300 roubles à son commerçant et chauffeur qui n'a pas ramené le scooter à temps. Une femme bouleversée donnera ses 20 000 dans un magasin plus agile, et une étoile sur Yandex.Market giflera cela. Le magasin peut offrir le meilleur service, mais le «dernier kilomètre» est effectué par des hommes sombres à Gazelles et Largus. S'ils se comportent mal avec les clients, le magasin ne pourra pas influencer cela.Dans le même temps, le magasin recherche généralement la livraison la moins chère - en ce sens que si vous payez encore moins les chauffeurs, ils iront travailler comme chauffeurs de taxi ou ailleurs. Les chauffeurs optimisent leurs gains quotidiens - vous devez transporter plus de commandes et ne pas être condamné à une amende. Si nous composons une fonction de coût global qui décrit le système dans son ensemble, alors cet état de la fonction correspondra certainement à son minimum local, le «puits potentiel».
Il y a clairement des problèmes systémiques importants dans cette fosse. Tout d'abord, le travail le plus difficile a été confié à l'employé le moins qualifié: le chauffeur contrôle la machine et planifie l'itinéraire et communique avec le client. Il porte également de l'argent. Il a des compétences et des spécialisations supplémentaires - par exemple, la capacité de livrer 30 commandes par jour dans une certaine zone. Il s'avère que l'entreprise doit former des conducteurs inexpérimentés et expérimentés à ne pas perdre, car ils (malheureusement pour l'entreprise) sont difficiles à remplacer.Deuxièmement, le processus de livraison est totalement imprévisible. Le client ne sait pas à quelle heure ils viendront à lui. Le client se voit généralement offrir de larges fenêtres de livraison - quatre, six heures ou plus. Cela lui crée de gros désagréments: il n'est pas toujours possible de s'asseoir au même endroit pendant six heures. Et même les conducteurs ne peuvent pas toujours accéder à ces fenêtres. La possibilité de rendre les fenêtres plus étroites pratiques pour les clients (deux heures ou mieux une heure) n'est possible que pour les grandes entreprises qui ont pu pousser plus fort et sauter d'un trou potentiel dans un état plus optimal. Nous parlons d'entreprises avec leurs propres livraisons et messagers. Des courriers «propres» seraient utiles à toutes les entreprises: de cette façon, vous pouvez contrôler la qualité de leur travail et même faire une sorte de vente incitative (lorsque le courrier offre à une personne quelque chose à acheter sur commande).Mais garder un personnel de messagerie coûte très cher - seules les plus grandes entreprises comme WildBerries ou Lamoda peuvent se le permettre.Troisièmement, les logisticiens trichent constamment. Les astuces telles que la surcharge des voitures et la rupture des quarts de travail des conducteurs sont considérées comme courantes (au lieu de 8 heures, elles fonctionnent 10-12). «Ce n'est pas grave - s'il ne rentre pas dans le volume, alors il mettra l'excédent dans la cabine» - même cela arrive. Pour cela, des amendes sont infligées, en particulier pour la surcharge des camions: à l'amende elle-même (à partir de cent mille roubles par entreprise) s'ajoutera une compensation pour les dommages à la plate-forme. Il est considéré comme une multiplication du coefficient de surcharge par une distance et peut facilement atteindre des centaines de milliers de roubles. Les propriétaires de flottes aimeraient conduire sans casser. Mais supposons que le logisticien ait le choix:- «Poussez la palette supplémentaire, un peu dépassée»- «Ajoutez la voiture supplémentaire, augmentez les coûts, mais sans casser»- «Asseyez-vous encore une demi-heure et faites un plan correctement»Souvent, il choisit la première.Un tableau aussi déprimant nous a inspiré un grand optimisme. Nous avons mené plusieurs entretiens avec des entreprises d'autres secteurs de la logistique, comme la livraison de gros produits, la livraison de documents. Toutes nos hypothèses selon lesquelles le monde n'est pas parfait en ce lieu ont été confirmées. Ainsi, devant nous, une grande fenêtre d'opportunité s'est ouverte. Nous nous sommes mis au travail avec impatience.Partie 4. MVRP et embouteillages
Voici les détails techniques de notre produit, commençons donc par la définition. MVRP est un problème de routage de plusieurs véhicules, c'est-à-dire une tâche dans laquelle vous devez parcourir de manière optimale plusieurs endroits, avec un parc de plusieurs voitures. Nous utilisons une terminologie dans laquelle une tâche similaire pour une seule machine est appelée SVRP (single VRP). Il se distingue du problème classique des vendeurs ambulants (TSP, problème des vendeurs ambulants) par la présence de fenêtres de livraison. Il ne semble pas y avoir de terminologie commune: dans l' article de Wikipedia, les tâches que nous résolvons sont appelées l'abréviation complexe VRPPDTW (VRP avec mode de ramassage et de livraison et fenêtres de livraison).Les programmes qui résolvent ces problèmes sont traditionnellement appelés «solveurs». Pour plus de polyvalence, vous devez mettre un tas d'options et de restrictions dans le solveur:Exemples d'options supplémentaires— , .
— (, ), .
— ( , ).
— . , : , .
— .
— .
— (, -), : . , * .
— «» , . , , - .
— : , .
Il existe plusieurs types d'algorithmes qui peuvent être utilisés dans les solveurs. Par exemple, il existe un grand groupe de solveurs universels open source et payants (Google OR-Tools, OptaPlanner, Choco-solver). Au sein de chacun d'eux, une fonctionnalité est construite et optimisée en tenant compte des restrictions requises. Ces solveurs sont généralement capables de résoudre tout un tas de tâches: tâches VRP, planification, allocation optimale des ressources dans le cloud.Il existe également de nombreuses solutions commerciales spécialement conçues pour les tâches MVRP et prêtes à être intégrées aux systèmes de gestion d'entreprise. VeeRoute, Maxoptra, Antor sont connus en Russie.Solveur Yandex.Routing utilise une combinaison d' algorithme de simulation de recuitet algorithme génétique. Nous ne savons pas ce que les concurrents utilisent, mais probablement quelque chose de similaire. Selon nos mesures, dans les tâches VRP, les solveurs de contraintes perdent beaucoup par rapport aux solveurs commerciaux.
Solution du problème TSP du rond-point des États en AmériqueJe ferai immédiatement une réserve: le sujet de la résolution du problème MVRP est si grand que dans l'article, nous n'en discuterons pas en détail, mais plutôt nous écrirons un article séparé.L'entrée principale d'un solveur est une matrice de distances entre les points impliqués dans la planification (points de commande plus un ou plusieurs dépôts). En fait, ce n'est pas une matrice, mais deux: par kilométrage et temps de trajet. C'est à travers ces matrices que l'optimisation se fait. Comme déjà mentionné, Yandex, contrairement aux développeurs d'autres solutions commerciales, dispose d'informations sur le trafic. Autrement dit, pour nous, la matrice n'est pas constante, mais change dans le temps, et nous en tenons compte dans le solveur. À notre connaissance, personne ne le fait dans le monde: même en sachant tout sur les embouteillages, il est difficile de construire un ensemble de matrices de distance avec une discrétisation raisonnable (suffisante pour s'assurer que les itinéraires résultants sont bons). Le fait est que le nombre de cellules matricielles croît de façon quadratique à partir du nombre d'ordres.Supposons que nous résolvons une tâche VRP pour livrer 10 000 commandes à l'aide d'une flotte de 500 voitures. Ensuite, nous obtenons deux énormes matrices qui changent dans le temps. Les télécharger uniquement sur le réseau prendra beaucoup de temps, mais leur contenu doit d'abord être calculé. Si cela n'est pas fait assez efficacement, nous devrons attendre quelques heures jusqu'à ce que les matrices soient construites et téléchargées, et ce n'est qu'alors que le solveur pourra être lancé. L'algorithme de Dijkstra nous aide ici: le calcul de matrices à grande distance peut être réalisé en un temps presque linéaire (à partir de la taille de la matrice). Mais notre équipe en parlera également dans un article séparé dans les prochaines semaines.Nous avons donc construit un solveur intelligent, l'avons parallélisé à un tas de voitures, créé un routeur avec des matrices de distance ultrarapides qui prennent en compte les embouteillages et avons également compris comment placer ces matrices dans le solveur. En conséquence, ils ont eu l'occasion en 15 minutes de résoudre le problème de la conduite autour de 3 000 emplacements. Résultat sur la carte:
Partie 5. Résultats et difficultés de mise en œuvre
Vous pouvez comparer nos itinéraires et ceux construits par des logisticiens qui planifient des voyages manuellement ou (parfois) en mode semi-automatique en utilisant les programmes des concurrents. Dans un cas typique, notre solution vous permet de battre les logisticiens en moyenne de 20% avec un petit parcours en optimalité. Dans le même temps, le temps pour obtenir l'itinéraire terminé est beaucoup plus court - 15 minutes au lieu de quelques heures. Dans un avenir merveilleux, le logisticien devrait passer d'une personne nerveuse et épuisée dispersant des ordres de voitures au milieu de la nuit, à un membre respectable de la société. Il utilisera notre planification automatique et corrigera occasionnellement les cas à bord unique avec ses mains.La mise en œuvre s'est déroulée de manière optimale lorsque les clients ont acheté notre solution au moment de l'ouverture de leur service de livraison. Mais la plupart de nos clients ne sont pas nouveaux. Ils ont déjà une solution mise en œuvre pour la logistique, et plus le client est grand, plus il a envahi toutes sortes de fonctionnalités des processus de cette entreprise en particulier, et juste des béquilles. Leur développement et leur support sont assurés par leur propre service informatique ou par un service informatique. On pense que les grandes entreprises (même si les avantages de notre produit leur sont évidents) ne peuvent implémenter le routage qu'avec une mise à jour majeure de l'infrastructure informatique. Et cela se produit généralement toutes les quelques années. En mai 2018, notre service nouveau-né a été annoncé lors de la conférence YaC 2018 en partenariat avec IKEA. Six mois plus tard, la mise en œuvre a commencé, nous avons commencé à échanger des données,et un an plus tard, lors de la conférence de l'industrie sur la logistique, le chef de projet chez IKEA a parlé des résultats.Les résultats ont été positifs, mais un peu inattendus pour nous. Par exemple, informer les clients augmente leur satisfaction et réduit considérablement le nombre d'appels au centre d'appels (avant, sans rien savoir du sort du canapé, les gens étaient nerveux et ont commencé à appeler).Ou un autre exemple - avec les travailleurs de l'industrie pétrolière., . , . , « » — . , , , «» ( , YouTube , ). , ( , ), , . : — , , , . . .
Autrement dit, il s'est avéré que notre installation initiale n'est pas entièrement correcte. Nous pensions que nous allions vendre un détour efficace de points, mais il s'est avéré que les entreprises ont besoin de produits différents qui affectent différents indicateurs, et pas seulement et pas tellement sur l'efficacité. Heureusement, nous en fournissons plusieurs autres avec le produit technologique de base.Les petites entreprises réussissent mieux à surmonter les difficultés d'intégration, mais peuvent être confrontées à des facteurs humains. Il est très difficile de convaincre le conducteur de suivre l'itinéraire prévu et de garder le téléphone avec l'application de suivi activée. Cela rappelle quelque peu les histoires de paysans du 19e siècle brisant des tondeuses et des charrues mécanisées. Bien sûr, tout n'est pas si triste, mais il y a une résistance au progrès.Conclusion
En peu de temps, nous avons réussi à construire un produit qui, nous l'espérons, va transformer toute la logistique du pays (ou du moins l'affecter fortement). Nos clients actuels et Yandex croient en nous. Ce dernier est également important: oui, le démarrage interne est plus calme que le démarrage en dehors de l'entreprise, mais nous devons également montrer le résultat.Nous avons commencé par mettre l'accent sur les grandes entreprises, dans nos plans futurs - pour abaisser le seuil d'entrée dans le service. Vous pouvez jouer avec la résolution de problèmes SVRP directement sur Yandex.Maps: lorsque vous ajoutez un quatrième point à l'itinéraire, le bouton "Optimiser" apparaît, qui appelle notre solveur.
Vidéo de la même histoire pour les étudiants du FCS en HSE:Tous les meilleurs itinéraires!