Discussion :

[grint54]

Une question pour les développeurs



Oui, comme je l'ai déjà signalé, je suis un passionné du web, mais, en amateur. Je suis entré par la petite porte dans ce vaste domaine et je ne code pas. Donc, puisque pour moi, le web est un passe-temps, j'ai pour autant un métier réel qui n'a rien à voir avec tout ça.

Mon métier est celui de chauffeur-livreur et, dans ce cadre là j'ai une question pour les développeurs puisque les chauffeurs dans une entreprise, sont les parents pauvres du secteur.

Voici le problème :


Faire une application dans le langage approprié pour faciliter la préparation d'une tournée de livraison pour la journée entière.

Les données :

Une journée de livraison débute en partant de Nancy et fini dans cette même ville.

• 41 clients à livrer
• 2 villes moyennes
• 5 gros bourg
• 12 villages

​
Entrons plus dans les détails

Les points de livraisons sont :

Neufchâteau(3 clients) - Liffol le Grand(2clients) - Châtenois(1 client) - Gironcourt sur Vraine(1 client) - Breuvannes(1 client) - Goncourt(1 client) - Colombey les Belles(1 client) - Mirecourt(3 clients) - Dompaire(1 client) - Vezelise(1 client) - Bourmont(1 client) - Bruyères(2 clients) - Rambervillers(3 clients) - Corcieux(1 client) - Grange sur vologne(1 client) - Lunéville(4 clients) - Baccarat(2 clients) - Dompaire(1 client) - Epinal(11 clients)

Sans aucune application spécifique, j'ai pu, avec le temps et l'habitude, faire ce genre de tournée exemple dans un minimum de temps. En faisant des erreurs, j'ai pu corriger avec le temps.

Pour l'instant, il n'y aurait sans doute pas besoin d'application vu les données. Il suffit de prendre une carte de la région à livrer, de la visualiser sérieusement et de tenter de faire le moins de kilomètres possibles pour boucler la livraison.

Un livreur qui se respecte tente, dans la mesure du possible, de ne pas revenir sur ses pas lors de sa livraison, et il préfère relier tous les points de la manière suivante :

Le tracé fait de légères courbes en arc de cercle façon escargot, il évite les cassures.(les zig-zags).

Là où ça se complique avec une ordonnée de plus, c'est les différents horaires d'ouvertures des clients.

Le livreur veut bien se lever tôt pour faire sa journée de livraison mais il n'aimerait pas être bloqué à son troisième ou quatrième client parce que celui-ci ouvre à 9 h00 alors qu'il se trouve déjà devant sa porte à 8 h00.

C'est là, où je me suis rendu compte, qu'il n'y avait pour le moment, que l'expérience humaine pour palier à tout ça.

La tournée avec les communes citées en haut, pourrait se faire de plusieurs manières, mais en tenant compte de tous les éléments, elle ne pourra être optimisé que d'une seule.

Le but d'une livraison est que le livreur ne doit pas être stoppé en attente inutile en plein milieu de son travail par un client encore fermé.

Je pense qu'il vous manque une donnée pour ceux qui voudrait relevé le défi. Je devrai signaler les horaires d'ouvertures de tous les clients pour l'optimisation finale. Mais déjà, voyons si mon billet intéresse quelqu'un, rien n'est moins sûr.

[ToTo13]

Ce que tu souhaites faire s'appelle le problème du voyageur de commerce : visiter tout les points possibles en un minimum de temps.
Il y a des heuristiques pour résoudre les gros problèmes de ce type.
Malheureusement, il te faudrait au préalable faire tourner cet algorithme sur une système de cartographie. C'est peut être facile, mais comme je ne connais... je ne peux pas me prononcer.

[grint54]

Oui ToTo13, c'est suite à la lecture du problème du voyageur de commerce que j'ai écris ce post. Je voulais y faire référence et j'ai oublié de mettre le lien.

Je ne pense pas que cet algorithme n'existe pas. C'est même sûr que ça existe, mais c'est certainement horriblement cher car vendu par des entreprises spécialisés en logistique, sur le web. Je ne suis pas un patron qui pourrait acheter ce logiciel pour ses livreurs, je suis dans la peau d'un salarié, ce n'est pas la même chose.

Disons que j'imagine seulement qu'un connaisseur, développeur pourrait nous apprendre un peu plus, sur cet algorithme qui est je le rappel : de faire un calcul de rapidité entre plusieurs points sur une carte de France, en tenant compte de plusieurs critères connus à l'avance.

Bon week-end et merci pour le déplacement de ce message

[tbc92]

L'aspect algorithme est un premier problème. On est à peu près dans le cadre du 'Voyageur de commerce', mais il faut des adaptations ( contraintes supplémentaires comme par exemple les heures d'ouverture de chaque contact, ou probablement les bouchons à prévoir à certaines tranches horaires.)
Disons que ce n'est pas insurmontable.
Ensuite, tu vas vouloir un programme 'fini', avec des écrans de saisie, des possibilités de sauvegarder les adresses des différents contacts, et tu vas vouloir que le programme calcule lui-même les temps de parcours (en accédant lui-même à google-maps par exemple).
Et donc tu vas avoir besoin d'un informaticien qui se débrouille en algorithme, mais aussi dans d'autres domaines. Et en plus, tu vas vouloir que le programme tourne sur des systèmes type 'téléphone portable', pour être consulté en cours de tournée.

Ca va coûter de l'argent... Si l'outil est vendu à plein de transporteurs, ça permet d'avoir des prix raisonnables. Et ça existe probablement. Mais un tel outil, développé sur mesure pour un transporteur unique... ça va être cher.

[DonQuiche]

Bonjour.

Il y a plusieurs approches possibles, le problème est qu'aucune ne va prendre en compte le fait qu'à 17h il faut éviter de passer par tel endroit, qu'en ce moment telle route est en travaux, que tu préfères passer par tel chemin au printemps, que tu aimes bien aller saluer la petite vendeuse de cette boutique-là le vendredi matin, quand elle n'a pas trop de clients. Or bidouiller le programme pour lui faire accepter ces contraintes serait aussi difficile que l'écriture initiale.

Du coup c'est se donner beaucoup de peine pour un résultat insatisfaisant.

D'autant que tu ne veux pas un simple algorithme sur un graphe à 41 noeuds : tu veux l'appliquer à une carte routière contenant des dizaines de milliers de rues et routes, pour lesquelles il faudra trouver un chemin. Déjà que le problème théorique avec fenêtres temporelles est difficile, tu dois en plus le coupler à un système géographique et à une recherche de chemin avec contraintes (vitesse des routes, feux rouges, stops, etc).

[dourouc05]

cet algorithme qui est je le rappel : de faire un calcul de rapidité entre plusieurs points sur une carte de France, en tenant compte de plusieurs critères connus à l'avance.

Non, ce n'est pas un algorithme : c'est un problème. Tu peux l'aborder de plusieurs manières différentes, avec plusieurs algorithmes ("recettes de cuisine", si tu préfères l'analogie). Chaque manière sera plus ou moins praticable dans ton coin.



Tu as l'option des heuristiques, qui nécessitent un bon niveau de codage (ou l'exploitation de logiciels existants, comme Concorde http://www.math.uwaterloo.ca/tsp/concorde.html, mais il faudra probablement traiter toi-même la question des horaires), puis des solutions plus tirées des mathématiques, avec des technologies comme la programmation mathématique (http://www.economicsnetwork.ac.uk/ir.../rasmussen.pdf pour les équations, http://lpsolve.sourceforge.net/5.5/PHP.htm pour la résolution, même depuis PHP) ou la programmation par contraintes (https://bitbucket.org/oscarlib/oscar...cp/VRPTW.scala avec des contraintes d'horaire).

Si tu fais des recherches, regarde aussi le mot clé VRP (plus général, puisqu'il considère plusieurs camions), voire VRPTW (avec des horaires). Tu pourrais tomber sur des offres comme https://logvrp.com/logvrpsite/, qui semble faire ce que tu souhaites avec une jolie interface mais payant, ou http://coral.ie.lehigh.edu/~larry/software/vrp-solver/, gratuit mais avec une interface moins léchée (issu de la recherche, sans volonté de commercialisation).

[grint54]

Merci à vous, vous avez bien cerné le problème. Vous avez même essayé de penser à tout (même un peu trop, à mon avis). Il n'y a besoin de prendre en compte les feux rouges, les crevaisons, et le bonjour à la jolie vendeuse. Tout cela existe réellement mais n'allons pas jusque là.

J'aimerais me faciliter la chose.

Jusqu'à présent et depuis le début de ma carrière de chauffeur-livreur, voilà ce qui se passe réellement, et c'est manuel, à l'inverse de numérique.

A chaque chargement, je prend un grand carnet et un crayon, je me dirige dans l'aire de mes colis à charger.

Rangées après rangées, clients après clients, je note le nom de chaque client et le nombre de colis pour ces clients. Je me suis arrangé à laisser un certain nombre de place vide pour les grandes villes. Car, dans l'aire de chargement, rien n'est rangé dans quelque ordre que ce soit. Si au final, il y aura 15 clients à Dijon, ils seront mélangés sur les rangées de palettes, ils seront intercalés avec des clients de petits villages.

Après avoir relevé tous les noms des clients sur le carnet, je vais m'installer à mon bureau de chauffeur-livreur, et, cette fois, je m'équipe d'un certain nombre de feuilles de chargement, vierges où l'on peut écrire au stylo un nombre de 10 clients.

Ensuite, de tête et avec l'expérience, je peux commencer d'ordonner ma tournée.

Par exemple, je sais de mémoire et d'habitude que en partant de Nancy, mon premier client ne devra pas forcément être le client le plus près de ma ville de départ. (ça pourrait, mais pas toujours)

Afin d'optimiser la durée totale d'une journée de livraison, le livreur d'expérience sait qu'il devra peut-être, suivant une configuration géographique et, en tenant compte des horaires d'ouverture des clients, commencer toujours au même endroit car c'est finalement là qu'il s'est aperçu, qu'il finissait sa tournée le plus tôt.

C'est tout un art.C'est l'humain qui décide, non un quelconque système numérique que j'appellerais de mes voeux.

Il faut savoir qu'une même tournée de livraison intervient tous les quinze jours et qu'il y 5 tournées par semaine.

Il est évident que je dispose d'un listing client complet, que je connais les horaires d'ouverture des clients et qu'en conséquence, sans un système numérique qui pourrait me faciliter la tâche, je me débrouille pas si mal que ça finalement.

Mais où est le problème alors ?

J'imagine que malgré tout ça, un programme au point serait un poil meilleurs que moi.

Il est possible que le sens, la direction de mon travail pourrait être amélioré car mon cerveau ne pourrais pas rivalisé avec la vérité numérique et qu'il y aurait certainement une petite heure à gagné sur l'ensemble d'une journée de livraison.

Je tiens à signaler, aux développeurs que je ne peste pas contre le fait que mon employeur ne m'est pas doté d'un tel système de calcul innovant, pour me faciliter le travail, ma question de départ demande si un tel système de calcul existe. J'ai lu que la réponse était oui. Je vois aussi que je ne pourrais pas, à mon niveau, investir dans un tel système, que ce n'est pas la priorité de mon employeur qui préfère améliorer au fil du temps, les employés des bureaux.

C'est pour cela que j'avais insisté sur le fait que les chauffeurs-livreurs étaient les parents pauvres dans l'entreprise. Des moyens numériques existent mais on préfère laisser les livreur avec des milliers de feuilles et un crayon, le tout avec répétition infinie.

Au dernière nouvelle nous allons être doté d'un iphone6 lecteur de QRcode pour soit disant nous faciliter la tâche. Je demande à voir!
Les vraies sociétés de transport sont doté d'un appareil qui coûte 1.500 €, parrait-il, trop cher pour mon entreprise. Ils ont choisis le système Iphone. Hors, avec ce smartphone, j'imagine que ce ne sera pas pratique pour une prise en main répétitive, alors que les appareils prévus pour ça, prennent le QRcode par le bout.

Ce système ne nous facilitera pas le travail, si nous devons continuer d'écrire nos listes à la main. Moi, perso, j'aurais aimé un système d'enregistrement de tournées et un moyen d'ajouter à chaque fois, le bon nombre de colis en regard du client.

Excusez pour ce texte long. Rassurez-vous, je suis de bonne humeur mais quand j'explique, j'explique longuement.