Optimiser la collecte, un problème NP complet complètement complexe

Dans le cadre de sa thèse, Stéphanie a étudié une association appelée RECYCLODROME. C’est une « ressourcerie » qui a pour vocation de récupérer les objets que l’on ne veut plus. Puis ils vont être valorisés pour être redistribués (vente) dans leur boutique, ceci afin de limiter la production des déchets. La majeure partie des objets qui passent par le RECYCLODROME provient de leur service de collecte : vous laissez votre numéro, votre adresse et vos disponibilités, et le RECYCLODROME se charge de vous rappeler pour convenir du jour de passage.

Une fois par mois

4748388431_eb0781dbf8Au début, la col-lecte était men-suelle. Elle s’ef-fectuait soit un jeudi, soit un vendredi dans le mois1. Le pro-blème pour les membres du RE-CYCLODROME était de déter-miner un jour qui conviendrait à un maximum de donateurs.

Tout d’abord, déterminer le jour ! Il se choisit en fonction du stock disponible à la « ressour-cerie ». Celle-ci travaillant en flux tendu, il ne faut pas manquer d’objets à valoriser et à revendre. D’autant que les clients apprécient la nouveauté. Une fois choisi, les membres de l’équipe vont prendre contact avec les futurs donateurs. Ces derniers vont alors confirmer ou infirmer leur disponibilité. Pour ceux que cela n’arrange pas, les équipiers vont proposer un autre jour. La date retenue sera au final celle qui aura remporté le plus grand suffrage. Il faut maintenant s’enquérir de l’heure de disponibilité et du lieu de résidence de tout ce petit monde et essayer de s’arranger au mieux pour contenter chacun, l’équipe du RECYCLODROME comprise.  En effet, Marseille est une ville particulièrement embouteillée2, il est donc important pour les membres du RECYCLODROME de limiter au maximum la distance qu’ils parcourent en ville pour éviter une balade du véhicule qui reviendrait au final à perdre son temps !

Supposons qu’ils aient déterminé une liste de donateurs chez qui ils devront se rendre durant la matinée. Les membres du RECYCLODROME cherchent alors le parcours le plus court pour aller à chaque domicile et revenir à la boutique. Vous l’avez reconnu, c’est le problème du voyageur de commerce. C’est un problème qui est très simple en apparence mais que même les plus grands mathématiciens/informaticiens3 ne peuvent résoudre en un temps raisonnable. Pour se rendre compte de la difficulté du problème, essayons de le résoudre de manière naïve dans un cas très simple.

Exemple
Un jeudi matin, deux des membres du RECYCLODROME doivent se rendre chez cinq personnes différentes et ils connaissent la distance qui sépare chaque domicile des autres puisque possédant les adresses. Quelle solution plus sûre y a-t-il que d’essayer toutes les combinaisons possibles et ensuite de choisir celle qui donne la distance la plus courte ?
Pour la première collecte, cinq choix sont possibles. Après la première visite, ils devront choisir un des quatre domiciles restants. Donc, pour chacune des cinq premières possibilités, il y a quatre choix à disposition. Nous en sommes déjà à 5 x 4 = 20 parcours possibles, vous suivez ? En faisant le même raisonnement pour les étapes suivantes, nous arrivons à un total de 5 x 4 x 3 x 2 x 1 = 120 possibilités !

Pour généraliser, si on appelle n le nombre de donateurs sur la liste, on obtiendra n x (n-1) x (n-2) x … x 2 x 1 = n!4 parcours possibles. Bien sûr, il existe des méthodes plus élaborées pour résoudre ce problème mais même celles-ci ne sont pas très rapides. Pour s’en convaincre, la meilleure méthode proposée actuellement calculerait environ 102 400 parcours différents avant de trouver le plus court dans le cas où les équipiers de la « ressourcerie » devraient se rendre chez 10 clients. Notre méthode, elle, calculerait 3 628 800 parcours… On a bien de la peine pour les membres du RECYCLODROME qui se trouvent confrontés à ce difficile calcul chaque semaine !

Deux fois par mois

Désormais, le RECYCLODROME effectue des collectes bimensuelles. On pourrait croire que cela leur facilite la tâche. Stéphanie avait même pensé à leur proposer l’idée suivante pour optimiser les prises de rendrez-vous : diviser Marseille en deux et proposer la collecte pour la moitié 1, le jour de la première quinzaine et pour la moitié 2, le jour de la deuxième quinzaine. Ce serait alors les donateurs qui téléphoneraient pour laisser leurs horaires de disponibilité en fonction de ces deux journées, un peu comme si on prenait rendez-vous chez le médecin. Ceci permettrait aux membres de la « ressourcerie » de ne plus passer autant de temps au téléphone. On pourrait même imaginer que ce serait la chargée de communication qui noterait les rendez-vous sur un planning dédié. Et pour arranger au maximum les futurs donateurs, on pourrait aussi faire en sorte que les deux moitiés de Marseille soit interverties un mois sur deux : la moitié 1 deviendrait la 2, et la moitié 2 deviendrait la 1.

Même si cela simplifierait les prises de rendez-vous  et permettrait aux équipiers de ne plus perdre leur temps au téléphone lorsqu’ils sont déjà à valoriser les objets, il n’empêche que cela ne résout en rien le problème du voyageur du commerce. À la limite, la distance parcourue lors d’une demi-journée de collecte va être réduite car les équipiers auront réduit la distance séparant chaque domicile où ils devront se rendre. Mais le temps de la recherche du parcours le plus court sera toujours aussi long5.

Vous l’avez compris, le problème du voyageur de commerce est extrêmement difficile à résoudre. Il appartient à la classe des problème que l’on appelle « NP-complet »6. Cette classe regroupe les problèmes dont on a prouvé qu’ils étaient très difficiles à résoudre. Il s’agit bien d’une preuve de la difficulté du problème et non pas simplement d’un argument du type : « Tous ceux qui ont essayé n’y sont pas arrivés ! Même les plus brillants ! » Car oui, en mathématiques, on arrive même à démontrer que ce n’est pas de notre faute si on ne trouve pas de solution à un problème. Par la même occasion, on prouve aussi que celui qui résoudra ce problème sera un véritable génie et méritera son prix d’un million de dollars reversé par l’Institut Clay, et peut-être un grand merci de la part des membres du RECYCLODROME ainsi que de tous les voyageurs de commerce, mais aussi et surtout de tous ceux qui veulent éviter de perdre leur temps dans les embouteillages marseillais !

crédit photographie : « Patience » par marcovdz sur flickr – Marseille

  1. La boutique ouvrant uniquement le mercredi, cela permettait à l’équipe de la « ressourcerie » d’avoir quelques jours pour valoriser les objets collectés avant de les vendre. []
  2. Marseille se classe au quatrième rang des villes les plus embouteillées du monde selon le site Tom Tom. []
  3. Ce problème se situe en fait à la frontière entre mathématiques et informatique théorique, si tant est que ces deux disciplines soient différentes, mais je ne rentrerai pas dans ce débat. []
  4. Prononcez « n factoriel ». []
  5. Mais alors, plus c’est court plus c’est long ? On pourrait s’y perdre, mais si l’on se perd cela rallonge encore le parcours… []
  6. Complexe, ça aurait tellement plus de gueule ! Enfin, ce n’est que le point de vue de la néophyte. []

2 réflexions au sujet de « Optimiser la collecte, un problème NP complet complètement complexe »

  1. « Pour s’en convaincre, la meilleure méthode proposée actuellement calculerait environ 102 400 parcours différents avant de trouver le plus court dans le cas où les équipiers de la “ressourcerie” devraient se rendre chez 10 clients. Notre méthode, elle, calculerait 3 628 800 parcours…  »
    Quelle est-elle ? avec quel paramètre (2 voyageur ? et 10 villes )
    Moi j’en ai programmé une il y a bien longtemps qui sans être optimale me semble plus efficace…
    Faudrait que je fouille mes archives

    1. Il s’agit en fait d’une hypothétique solution qui utiliserait la programmation dynamique proposée par Held et Karp. La complexité serait en O(n^2 2^n). Les paramètres seraient 1 voyageur et 10 villes. Bien sûr, pour des petites instances comme celle-ci, on peut toujours trouver mieux que les solutions optimales pour de grandes instances. Ça me rappelle mes cours de complexité algorithmique où l’on avait vu qu’un algorithme qui procède à 10n opérations sera moins efficace qu’un algorithme qui a besoin de n^2 opérations pour n 10.

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *