Je veux partager avec vous l'expérience de la création d'un système logistique dans une société commerciale.
Un beau jour, vers 2012, le chef s'est fixé la tâche: réfléchir au problème de l'optimisation des coûts de logistique de transport de l'organisation.
Le principal domaine d'activité de l'entreprise est la vente en gros et la livraison de produits, où les coûts de transport occupent une part importante des coûts.
La direction a estimé que le moment était venu de mettre les choses en ordre pour dépenser de l’argent sur le carburant, et on soupçonnait également que les chauffeurs étaient également impliqués dans la livraison «à gauche» entre les vols. Dans les petites et moyennes entreprises, beaucoup repose sur la confiance, car garder les individus sous contrôle n'est pas rentable et n'est pas toujours conseillé. Lorsque les coûts augmentent et que l'efficacité diminue, il vous suffit de faire quelque chose.
Pour commencer, nous avons essayé de résoudre le problème par des méthodes de gestion: mesure continue du niveau de carburant, lectures du tachymètre, mesure du temps de livraison avec accompagnement personnel de la cargaison. L'effet n'était rien d'autre que de la négativité, de la suspicion et des mouvements inutiles (mesurer cela est aussi un travail pour quelqu'un). S'il était encore possible de déterminer une portée approximative avec une seule route, puis avec un vol de 25 à 35 installations de vente au détail, tout a beaucoup changé, la propagation était très importante, à la fois en temps et en carburant.
Objectif: envoyer des véhicules occupés aux commerces, en réduisant le kilométrage et donc les coûts. Si possible, évitez tout écart par rapport à l'itinéraire. L'objectif est de réduire les coûts avec un investissement minimal en temps de financement et de mise en œuvre, pour ainsi dire hier. Au cours des discussions, ils se sont mis d'accord sur plusieurs alternatives:
- utiliser l'un des services pour calculer les itinéraires et comptabiliser le carburant et les lubrifiants;
- mettre sur les modules de suivi / suivi de flotte;
- concevez quelque chose vous-même;
Nous avons décidé d'essayer les trois solutions et de choisir la meilleure:
1. A cette époque, nous n'avions pas trouvé de bonne solution clé en main. Soit une conception clé en main, mais coûteuse, soit à prendre telle quelle et plus loin par accord. J'ai essayé plusieurs services en ligne. Dans l'ensemble, ce n'est pas mal, mais en gros la difficulté était de dupliquer les informations du système comptable, le nombre d'actions pour obtenir le résultat (cliquer ici, aller ici, mettre à jour le répertoire), tout est en ligne (à l'époque c'était critique). Mais le plus gros inconvénient est la difficulté de créer des itinéraires avec de nombreux points et de choisir le meilleur itinéraire. Habituellement, tout devait être sélectionné manuellement, en ajustant les valeurs, ce qui était long et pas toujours réussi en conséquence.
Après quelques mois de travail, ils ont refusé cette décision.
2. À titre expérimental, ils ont installé des modules de suivi GSM sur une douzaine de voitures.
Le résultat est plus réussi. Vous savez toujours où était la voiture. Mais le coût est plus cher que la première option. Cependant, après avoir identifié quelques cas de déviation de l'itinéraire (un chauffeur de chabbat, le second a rendu visite à la dame du cœur, pendant les heures de travail), les employés ont commencé à se débarrasser de ces appareils de manière intensive. Bien qu'ils n'aient pas accepté cette innovation avec enthousiasme auparavant. Soit la borne d'alimentation a clignoté accidentellement, soit lors de la réparation du moteur, l'appareil est tombé en panne ou l'électronique a "surchauffé" au soleil. Donc, pendant trois ans, nous avons perdu 9 appareils. En général, la décision s'est avérée positive, mais des inconvénients - j'ai dû regarder les itinéraires parcourus pendant longtemps pour identifier les activités suspectes, ce qui n'est pas très pratique. Un avantage du système de suivi était l'élément sur l'exportation de la piste, qui permettait d'accumuler certaines statistiques sur les itinéraires.
Plus tard, nous avons utilisé un autre système de l'un des principaux opérateurs de téléphonie mobile pour les communications d'entreprise et le suivi de l'activité des agents commerciaux, le résultat était similaire: les cartes SIM se cassaient, les téléphones étaient perdus, ils étaient oubliés à la maison, la batterie était épuisée, les gens trouvaient toujours une issue.
3. Parallèlement aux deux premières approches, nous avons décidé d'
inventer un vélo , pour réaliser dans notre système comptable la possibilité de construire nous-mêmes des itinéraires.
Tout d'abord, nous avons apporté tous les lieux de visite et entré leurs coordonnées géographiques dans la base de données. Nous avons obtenu les coordonnées selon le tracker GPS lors de la visite, ainsi que visuellement à partir des cartes
OSM , en trouvant le bon endroit avec la souris et en copiant les coordonnées.
Au deuxième stade, il a fallu obtenir des cartes vectorielles de la région dans un format pratique.
Le choix s'est porté sur le même OSM, car les cartes ont un format ouvert. Nous ne maîtrisions pas le dépotoir de la planète, nous avons donc initialement téléchargé les données en morceaux au format XML, via l'exportation à partir de l'OSM lui-même, puis connecté les territoires. Plus tard, je suis tombé sur un projet
GIS-LAB . Ces braves gens ont pendant de nombreuses années aménagé un
dépotoir quotidien de territoires, répartis par région. Mais tout le monde veut manger, le projet est au point mort depuis peu, et les gars ont
déménagé , et ils font le même travail à un prix raisonnable.
Après avoir reçu la carte au format XML, nous avons extrait la couche responsable des routes selon les
spécifications . Le volume de cartes de plusieurs régions voisines occupant dix gigaoctets, l'analyseur SAX a été écrit en RUBY, il n'a sélectionné que les balises nécessaires et a fusionné les régions voisines dans lesquelles les activités étaient menées dans une seule structure.
Le projet lui-même est écrit en tant que DLL externe au système comptable écrit en Pascal. La flotte d'appareils sur laquelle le système était censé fonctionner était, pour le moins, obsolète, il y avait donc une limite de 1 Go de RAM (Oui, il y a aussi des entreprises qui utilisent cette technique, travaillent depuis 10 ans et fonctionneront la même quantité). Initialement, il y avait un désir de casser la carte en morceaux et de la charger dans la RAM selon les besoins (comme sur les navigateurs), mais c'était extrêmement lent. En conséquence, nous avons réussi à composer jusqu'à une cinquantaine de Mo raisonnables.
Dans OSM, les cartes routières sont représentées comme des sections vectorielles de la route avec des attributs supplémentaires. Dans notre décision, nous avons utilisé des
listes d'adjacence . Où le pic est un point sur la carte et les bords sont les chemins vers un point voisin. Pour l'optimisation, nous pensons qu'il peut y avoir un maximum de quatre chemins (intersection) à partir d'un sommet. S'il y a plus de 4 chemins, vous devez diviser le bord en deux chemins supplémentaires, nous avons donc toujours un nombre fixe de bords = 4 pour chaque point de carte. Cette approche nous permet d'aligner les données en mémoire, bien qu'elles soient quelque peu redondantes.
Il convient de noter que la Terre n'est pas une boule (de manière inattendue), mais un
géoïde , mais à des fins de cartographie, elle est simplifiée en sphéroïde ou
ellipsoïde .
Pour nos besoins, j'ai trouvé une formule pour calculer les distances entre deux points sur la surface d'un ellipsoïde, dont je ne pouvais pas comprendre la signification la plus profonde, mais cela ne nous empêche pas de l'utiliser.
codefunction distance(StartLong:Single; StartLat:Single; EndLong:Single; EndLat:Single) : Single; const D2R: Double = 0.017453;
Après avoir créé la base de la route, une couche visuelle était nécessaire pour afficher la zone environnante. Le projet
maperitive a aidé
ici , il
nous a permis
d'analyser la carte OSM des régions en sections de tuiles par couches d'approximation, tout comme 10 ^ 100 ou Yandex. Il y a eu une tentative de travailler avec les cartes des géants en ligne, en affichant une carte vectorielle au-dessus de la couche du navigateur, mais en raison des restrictions de licence, ils ont décidé de refuser. En conséquence, nous avons créé un disque virtuel et téléchargé un vidage de tuiles sur quelques dizaines de gigaoctets, mais tout est à portée de main et ne ralentit pas. Certes, environ une fois tous les six mois, vous devez vous rafraîchir, cela coïncide généralement avec la surcharge des cartes.
Pour combiner l'image de la tuile et la carte vectorielle, vous devez savoir que les tuiles, Google, OpenStreetMap, Bing, Yahoo sont représentées dans la
projection Mercator (plus précisément
WEB MERCATOR , qui est la projection sur la sphère), où chaque couche plus profonde est deux fois plus détaillée que la précédente.
Yandex.Maps utilise la projection de l'ellipsoïde Mercator.
Peu importe que vous puissiez recalculer les coordonnées géographiques sur le plan de projection et vice versa.
Nous avons choisi le niveau 17 de détail comme maximum. Closer n'a aucun sens en raison d'une augmentation du stockage du nombre de tuiles (chaque niveau est 4 fois plus grand que le précédent), ainsi que de leur faible contenu en informations.
2 ^ 17 * 256 = 33554432 (256 est la taille du bord de la tuile en pixels).
Maintenant que nous avons les outils de base, nous pouvons passer directement à la tâche de créer l'itinéraire optimal. Nous connectons les centres commerciaux avec le bord le plus proche du graphique routier, puis commençons la recherche du chemin le plus court. Pour ce faire, nous utilisons une variation de
l'algorithme de
Dijkstra pour sa variation déchargée séquentiellement pour chaque point de visite. En sortie, on obtient une
matrice d'adjacence de taille (N + 1) * (N + 1) à l'infini sur la diagonale principale (ban ring), où N est le nombre de points de visite sans tenir compte du point de sortie.
La matrice résultante stocke la distance minimale le long des routes entre tous les centres commerciaux, ce qui est un
problème classique de
vendeur ambulant . Étant donné que la complexité algorithmique d'un tel problème est exagérée, nous avons utilisé
la méthode branch et bound pour le résoudre. Pour n <15, il est exhaustif, sinon une estimation grossière est connectée en profondeur. L'option n'est certainement pas idéale, mais fonctionne bien.
En conséquence, nous avons obtenu un itinéraire proche de la distance optimale avec une estimation en km. Si nécessaire, l'opérateur peut modifier manuellement l'itinéraire en faveur de la priorité des points individuels.
La solution fonctionne dans l'organisation depuis environ 7 ans, avec un certain succès, mais non sans défauts, tant en termes de précision que de commodité. Les résultats sont cohérents avec les données de suivi GPS des véhicules. À mon avis, l'introduction de la logistique a permis d'économiser 10 à 12% des fonds alloués pour le carburant. Le programme a été conçu, lancé et accompagné par une seule personne - votre humble serviteur.
Ma direction conservatrice n'est pas désireuse de «briller», alors je suggère un exemple fictif de la voie à suivre.
Sans visualisation, le calcul est plusieurs fois plus rapide et à l'intérieur d'un règlement, presque instantanément.
Après tant d'années, il est parfois difficile de saisir le code et de le copier avec une nouvelle expérience sur une nouvelle plate-forme plus moderne, mais jusqu'à présent, il n'y a aucune faisabilité économique.
C'est tout ce que je voulais vous dire, j'espère que c'était intéressant.
Je m'excuse si je n'ai pas été précis quelque part.