Vous consultezLe secteur du transport interurbain et la recherche opérationnelle : une synergie méconnue à exploiter

AuteursYves Nobert du même auteur

La répartition de charges entre des camions

5 Comme première illustration de la méthode scientifique, considérons une entreprise de transport à charges entières (truck load) connaissant un problème de cueillette. Supposons que l’entreprise dispose de sept camions (T) actuellement situés dans les sept villes indiquées dans le schéma 1, et que sept charges (P), correspondant chacune à la capacité d’un camion, doivent être cueillies aux endroits mentionnés dans le même schéma. Dans cet exemple, chaque charge sera attribuée à un seul camion et chaque camion prendra une seule charge, qu’il ira chercher au lieu indiqué et qu’il amènera à sa destination finale ou encore à un terminus. Évidemment, on cherche à minimiser les distances parcourues sans chargement par les camions entre leur position actuelle et le lieu de la cueillette qui leur sera assignée. Le tableau 1 donne les distances (en kilomètres) entre les villes où sont les camions et celles où sont les charges.

Affectation de camions : carte des villes

Affectation de camions : carte des villes

Tableau 1 - Affectation de camions : distances entre les villes (en kilomètres)

6 Typiquement, un répartiteur, utilisant un logiciel comme MacPoint, placera camions et charges sur une carte informatisée (voir le schéma 1, où P représente une charge et T, un camion) et attribuera séquentiellement les charges aux différents camions. Il donnera évidemment la priorité aux combinaisons les moins coûteuses, recherchant dans le tableau 1 les valeurs les moins élevées. Le plus souvent, il retiendra au tout début les combinaisons 3-7 (le camion 3 situé à Franklin ira cueillir la charge 7 à Newton), puis 7-4 (Newark-Paterson). La suite est moins évidente

7 Ce problème a été présenté en conférence à plus de 80 répartiteurs expérimentés, qui ont construit manuellement des solutions dont la distance totale sans chargement s’élevait la plupart du temps à 540 kilomètres ou plus. Une «bonne» solution intuitive est illustrée au schéma 2. Elle implique que les camions parcourent au total 541 kilomètres sans chargement.

Affectation de camions : une solution intuitive

Affectation de camions : une solution intuitive

8 Mais il est possible de faire mieux! En effet, la solution optimale ne requiert que 462 kilomètres de déplacement sans chargement. Il s’agit de choisir les combinaisons 1-6, 2-7, 3-3, 4-1, 5-5, 6-4 et 7-2. Pourquoi est-ce que peu d’opérateurs humains réussissent à trouver cette solution? Quelle est la faille dans l’approche intuitive utilisée couramment qui conduit à un excédent de coûts?

9 La faiblesse de l’approche intuitive réside essentiellement dans l’aspect séquentiel des choix. L’humain, même dans un exemple simple où seulement 7 camions ont à cueillir 7 charges, ne peut considérer toutes les possibilités. Mentionnons que, dans cet exemple, il existe

10

11 façons d’affecter les 7 camions aux 7 charges. Si nous avions considéré 20 camions et 20 charges, le nombre de solutions possibles s’élèverait à 20!=2 432 902 008 176 640 000. Il est donc trop long, voire impossible, pour un humain de les envisager toutes. Le répartiteur doit se rabattre sur une stratégie où il «divisera pour régner» : il traite donc les affectations une à une. En un premier temps, il choisit la donnée la moins coûteuse dans le tableau des distances. Dans notre exemple, il s’agit du nombre 25, qui représente la distance entre Franklin et Newton. Notre opérateur décide donc que le camion 3 situé à Franklin ira à Newton. Ensuite, il biffe la ligne Franklin et la colonne Newton, puis recommence le processus avec le tableau réduit. Cette fois, la donnée la moins coûteuse est le nombre 26 à l’intersection de la ligne 7 (Newark) et de la colonne 4 (Paterson) : la deuxième décision consiste donc à affecter le camion 7, situé à Newark, à la charge 4. On biffe alors la ligne 7 et la colonne 4. On répète ces opérations jusqu’à ce que tous les camions aient été affectés. Malheureusement, on se retrouve à la fin avec des choix très coûteux, mais incontournables. Des répartiteurs astucieux effectuent divers ajustements en cours de route pour esquiver les pièges qu’ils pressentent, pour éviter de se retrouver coincés à la fin avec des affectations forcées qui sont fort onéreuses. Mais ils ne peuvent tout prévoir

12 En pratique, les solutions intuitives obtenues par des gens même expérimentés sont souvent inefficientes. Dans l’exemple considéré, la «bonne» solution intuitive typique exige un parcours total sans chargement de 541 kilomètres, ce qui représente environ 17 % de plus que la solution optimale.

13 Et encore! Le problème traité était de petite taille. De plus, diverses difficultés pratiques ont été volontairement ignorées. Dans la réalité, les camions sont de plusieurs types. De même, les clients imposent parfois des fenêtres de temps : le camion doit venir chercher la charge ni trop tôt ni trop tard. La prise en considération de ces contraintes alourdit considérablement la tâche du répartiteur, ce qui l’amène souvent à proposer des solutions qui s’éloignent encore plus de l’optimum. La qualité des solutions construites selon l’approche scientifique est peu réduite ou ne l’est pas du tout par ces contraintes additionnelles. De fait, dans bien des cas, elles impliquent seulement d’éliminer certaines entrées du tableau des distances. Dans l’approche scientifique, elles interviennent uniquement dans la phase initiale du calcul des données du tableau et ne reviennent plus dans les étapes ultérieures de l’optimisation. Or, le plus souvent, un ordinateur exécute rapidement la phase initiale, que des contraintes additionnelles soient présentes ou non.

14 Mais comment procède cette extraordinaire approche scientifique? Précisons d’abord qu’énumérer toutes les possibilités exigerait un temps excessivement long, même pour les ordinateurs d’aujourd’hui, à moins que la taille n du problème ne soit faible. Par exemple, quand n=20 camions qui doivent être affectés à autant de charges, il y a, avons-nous mentionné ci-dessus, 20! possibilités. Si on présume (de façon optimiste) qu’un ordinateur traite un milliard de possibilités à la seconde (autrement dit : une possibilité par nanoseconde), il faudrait 20! nanosecondes, soit un peu plus de 77 ans, pour considérer une à une chacune de ces possibilités Il n’est pas sûr que les clients attendraient patiemment que l’ordinateur trouve ainsi l’affectation la moins coûteuse.

15 La caractéristique essentielle de l’approche scientifique, c’est la traduction du problème concret en un modèle mathématique. Le lecteur intéressé trouvera en annexe le modèle associé au problème de répartition du tableau 1. Il faut également colliger les données numériques pertinentes (dans notre problème de répartition, il s’agirait de déterminer les entrées du tableau 1), puis résoudre le modèle. Pour cette dernière opération, il existe sur le marché plusieurs outils informatiques. Il est parfois nécessaire de les adapter ou d’en élaborer de nouveaux.

16 Le temps de calcul des algorithmes et des heuristiques dépend évidemment de la taille du problème, mais aussi de façon cruciale de certaines caractéristiques mathématiques des modèles, que le jargon scientifique résume sous le vocable de «complexité». Certains problèmes, comme l’affectation de n camions à n charges, se résolvent rapidement : le temps de calcul augmente assez lentement avec la taille n. Dans d’autres cas, tel le problème du voyageur de commerce traité plus loin, le temps de calcul peut, en théorie, augmenter de façon explosive avec la taille.

17 À titre d’illustration, nous avons résolu[2] [2] Nous avons utilisé à cette fin un ordinateur portatif...
suite quelques exemples numériques des problèmes d’affectation et du voyageur de commerce. Le tableau 2 donne les temps de calcul, selon la taille n, lorsque les mêmes données sont traitées par l’un ou l’autre des modèles scientifiques classiques utilisés pour résoudre optimalement ces problèmes. On notera que une seconde suffit quand la taille est très petite (n=10), que le temps de résolution des problèmes d’affectation augmente lentement avec la taille, mais que celui du problème du voyageur de commerce explose littéralement.

Tableau 2 - Temps de calcul selon la taille n

L’élaboration d’horaires

18 Une entreprise, dans le but de construire de «meilleurs» horaires, a analysé les tâches à effectuer pendant une certaine période et a calculé ses besoins minimaux en personnel. Le tableau 3 décrit les résultats obtenus pour une catégorie d’employés et une journée particulières. Il s’agit maintenant de déterminer combien d’employés seront appelés au travail et quelles plages horaires on leur offrira, sachant que la convention collective limite l’entreprise à des plages d’au moins 4 heures et d’au plus 10 heures. Pour simplifier, nous supposons ici que les employés travaillent durant toute la plage horaire pendant laquelle ils sont présents, sans arrêt ni pause.

Tableau 3 - Besoins minimaux en personnel, par période de 15 minutes

19 Essayons de construire un «bon» horaire pour combler les besoins minimaux du tableau 3. Il est naturel de faire appel à 2 employés en début de journée; ces 2 personnes resteront aussi longtemps qu’au moins 2 employés seront requis, à moins que les contraintes syndicales n’amènent à faire des ajustements. Ici, ni le minimum de 4 heures ni le maximum de 10 heures n’influent sur la durée de l’affectation de ces 2 premières personnes : en effet, le plancher de 2 employés est valide jusqu’à 13 h 00 inclusivement. La première plage horaire de notre solution (voir le tableau 4, section de gauche) s’étendra donc de 6 h 30 à 13 h 00, soit une durée de 6 heures 30 minutes. Il faut ajouter 1 employé à partir de 7 h 15, car les besoins minimaux augmentent à 3 durant la période de 7 h 15 à 7 h 30; ce 3e employé travaillera pendant 4 heures (on serait tenté de lui demander de partir à 10 h 45, mais on irait alors à l’encontre du minimum de 4 heures imposé par la convention collective; noter également que le 3e poste requis entre 11 h 00 et 12 h 30 pourra être comblé sans frais additionnels par les personnes qui débuteront à 8 h 45 ou à 9 h 45 pour satisfaire à l’augmentation des besoins minimaux observée à ces moments-là). On poursuit en invitant un 4e employé de 8 h 45 à 12 h 45 et un 5e de 9 h 15 à 13 h 30 Le tableau 4, dans sa section de gauche, décrit l’horaire ainsi obtenu pour la journée. On constate que 9 employés seront appelés ce jour-là et qu’ils travailleront au total durant 59,75 heures.

Tableau 4 - Solutions au problème d’horaire

20 Est-il possible de faire mieux ? On pourrait peut-être grignoter quelques quarts d’heure en analysant soigneusement les moments où certains employés sont en surplus selon l’horaire proposé. Mais ces améliorations ne sont pas évidentes et exigent du temps de réflexion. Or, le responsable des horaires doit préparer un horaire quotidien pour chacune des 43 fonctions de l’entreprise, puis un horaire hebdomadaire pour chacun des employés. Il est donc exclu pour lui de peaufiner longuement chacun d’entre eux. La méthode scientifique, une fois que le système est en place, produit les 43 horaires quotidiens en quelques minutes. Dans le cas des données du tableau 3, on obtient la solution optimale décrite au tableau 4, qui exige 9 employés et 53,25 heures. Il s’agit d’un gain de 6,50 heures, soit 10,9 %, par rapport à la solution intuitive.

21 La méthode scientifique peut tenir compte sans difficulté des pauses-repas et des heures supplémentaires. Il est également possible de construire des horaires hebdomadaires ou mensuels pour chaque employé et de prendre en considération diverses contraintes qualitatives, telles les priorités accordées à certains employés.

Le problème du voyageur de commerce : la cueillette de colis par un camion

22 Considérons une entreprise de transport à charges multiples (less than truck load) qui planifie les cueillettes d’une journée donnée. Elle doit envoyer des camions chercher les colis chez les clients de façon à respecter diverses contraintes, dont voici quelques exemples typiques :

23 – Chaque client est visité par un seul camion.

24 – Les colis attribués à un même camion ne doivent pas en excéder la capacité.

25 – L’itinéraire d’un camion donné ne doit pas dépasser une certaine durée, par exemple huit heures.

26 – Il faut respecter certaines fenêtres de temps.

27 L’entreprise doit décider combien de camions seront utilisés, quels colis ira chercher un camion donné et dans quel ordre. Il s’agit d’un problème difficile que l’on cherche généralement à résoudre en trois étapes, plus ou moins explicitement distinguées :

28 – Calculer un tableau des distances entre les différents points à visiter. Ces données de base sont la clé des étapes ultérieures. Il est donc important que les valeurs du tableau soient le plus près possible des valeurs réelles. Il existe plusieurs logiciels[3] [3] Par exemple, Pc Miler ou Rand McNally. ...
suite qui permettent d’obtenir de telles distances; certains sont excellents, mais d’autres recourent à des approximations grossières. Par exemple, certains logiciels utilisent, pour estimer la longueur d’un trajet urbain, la distance à vol d’oiseau; il s’agit là d’une valeur souvent fort inexacte, car elle ne tient nullement compte des sens uniques, des interdictions de tourner à gauche, etc.

29 – Diviser l’ensemble des clients en groupes (clusters), les membres d’un groupe étant tous attribués à un même camion.

30 – Pour chaque groupe, construire un itinéraire qui indique l’ordre selon lequel seront visités les clients du groupe.

31 Nous nous attardons maintenant à ce troisième et dernier problème, qui a reçu le nom de problème du voyageur de commerce dans la littérature scientifique. Nous supposerons que le coût est proportionnel à la distance parcourue. Nous supposerons également, comme dans le problème classique du voyageur de commerce, qu’aucune fenêtre de temps n’est imposée par les clients[4] [4] Il est possible de construire des modèles scientifiques...
suite.

32 Nous avons donc un certain nombre de clients, qui doivent être visités par le camion. Nous illustrerons notre propos à l’aide de l’exemple décrit au tableau 5, qui comprend un terminus et 14 clients représentés par des points dans un plan cartésien. Le camion doit partir du terminus, visiter chacun des 14 points-clients une seule fois, puis revenir au terminus. Enfin, nous cherchons à minimiser la distance totale parcourue par le camion, la distance entre deux points étant supposée égale à la distance à vol d’oiseau.

Tableau 5 - Problème du voyageur de commerce : localisation du terminus et des clients

33 Des gens expérimentés, s’ils disposent de suffisamment de temps, trouvent généralement d’assez bonnes solutions intuitives à un problème de ce genre. L’œil humain est relativement efficace pour tracer de tels itinéraires. Mais, en pratique, le temps presse, le nombre d’itinéraires à construire est élevé, on aimerait raffiner la solution du deuxième problème de la répartition en groupes en testant les itinéraires découlant de plusieurs regroupements. Conclusion : il serait souhaitable de confier la tâche de la construction des itinéraires à un ordinateur.

34 Supposons donc qu’on demande à un programmeur, qui n’est pas versé en recherche opérationnelle, d’écrire un logiciel pour construire un tel itinéraire. Le programmeur doit remplacer l’intuition visuelle de l’opérateur humain par une approche systématique qui choisit la suite des points à visiter à partir de principes abstraits. Dans bien des cas, il cherchera à joindre le point courant à son voisin immédiat. Dans l’exemple des données du tableau 5, le camion partirait du terminus T, puis se rendrait successivement aux points 3, 14, 5, 11, 7, 12 et 6. Le choix entre 8 et 13 comme prochain client à visiter n’est pas évident visuellement et il faut calculer les distances pour départager les deux candidats. Il s’avère que c’est 8 qui est le plus près et qui, par conséquent, sera la prochaine étape de notre itinéraire. Celui-ci se poursuit avec les points-clients 4, 9 et 1. Là, le camion est coincé et il lui faudra aller loin pour trouver le plus près des clients qui n’ont pas encore été visités; ce sera le client 13. L’itinéraire se termine avec les points 2, 10 et le terminus T auquel il faut nécessairement revenir. Voici, en résumé, l’itinéraire qui résulte du critère du voisin immédiat utilisé ici :

35

36 La longueur totale de cet itinéraire est de 117 unités environ. Il serait facile, à vue d’œil, d’améliorer cette solution : par exemple, il serait plus efficace, une fois en 13, de visiter la ville 10 avant la ville 2, puis de retourner au terminus. Mais un tel changement requiert une intervention humaine et, comme nous l’avons mentionné précédemment, on préfère généralement confier la construction d’itinéraires à un ordinateur. Puisque l’approche intuitive «gloutonne» donne des itinéraires inefficaces, on devra la remplacer par une approche plus sophistiquée. L’une d’entre elles consiste à utiliser un modèle linéaire approprié, qu’on résout à l’aide d’un logiciel, tel LINGO. Pour l’exemple numérique du tableau 5, un itinéraire optimal, obtenu de LINGO, est le suivant :

37

38 dont la longueur totale est de 98 unités environ. Le critère du voisin immédiat donne ici un itinéraire dont la longueur totale représente 120 % de la longueur totale minimale. Comme on l’a illustré ci-dessus, il est souvent possible d’améliorer manuellement l’itinéraire fourni par le critère du voisin immédiat, mais de tels changements exigent temps et efforts. Il est beaucoup plus facile – et efficace – de recourir à un logiciel spécialisé, pour autant qu’on puisse trouver un tel logiciel dans le système informatique de l’organisation (voir les schémas 3 et 4).

Problème du voyageur de commerce : localisation du terminus et des clients

Problème du voyageur de commerce : localisation du terminus et des clients

Solution intuitive

Solution intuitive

Conclusion

39 Nous avons illustré trois situations concrètes où le recours à des modèles de la recherche opérationnelle permet d’améliorer significativement les opérations d’une entreprise de transport. On parle évidemment de réduction des coûts. Mais il est également possible de tenir compte dans ces modèles de contraintes qualitatives que les méthodes utilisées dans la pratique ignorent souvent, à cause de la difficulté qu’elles ont à trouver des solutions qui satisfont à la fois aux contraintes de base et à ces contraintes additionnelles.

40 Les méthodes actuellement utilisées dans la pratique font souvent appel à des stratégies qualifiées de «gloutonnes» par les spécialistes. Parce que les problèmes sont de grande taille et que l’esprit humain n’arrive pas à considérer le problème dans son ensemble, on doit décomposer celui-ci en étapes simples – principe cartésien bien connu –, puis on détermine la meilleure solution locale pour chacune des étapes. Ainsi, dans le premier exemple qui traitait de l’affectation des camions aux charges, on a constaté que choisir séquentiellement les paires camions-charges les plus rapprochées amenait à un cul-de-sac. Or, localement, pourquoi ne pas attribuer une charge donnée au camion situé le plus près? L’erreur n’est pas là. Elle est dans le regroupement de ces solutions locales. La stratégie consistant à «diviser pour régner» ne fonctionne pas ici : selon l’approche gloutonne, on a considéré séparément chaque attribution et, lors de chaque étape, on a retenu la paire camion-charge la plus rapprochée parmi les camions et les charges non encore attribués; mais comme on l’a déjà constaté, l’ensemble de ces paires ne constitue pas une solution globalement optimale. Autrement dit, en «recollant» les solutions locales, on n’obtient pas nécessairement une solution qui soit optimale globalement. Il arrive parfois que l’approche gloutonne fournisse une solution optimale. Mais, comme l’illustrent les trois exemples présentés ici, elle fournit le plus souvent des solutions sous-optimales. Or, si on procède manuellement, il est difficile de faire mieux.

41 Les entreprises de transport auraient donc intérêt à intégrer l’approche scientifique de la recherche opérationnelle à leur banque d’outils informatiques. Après une phase d’adaptation inévitable, elles obtiendraient grâce aux modèles de la recherche opérationnelle des solutions qui seraient moins coûteuses, qui seraient plus faciles et moins longues à calculer et qui, en tenant compte de diverses contraintes qualitatives additionnelles, permettraient d’améliorer le climat de travail et le service aux clients.

Annexe

Notes

[ 1] «Au cours des 10 dernières années, la productivité aux États-Unis s’est accrue en moyenne de 1,97 % par année contre seulement 1,08 % ici» (Michel van de Walle, Le Journal de Montréal, 15 mars 2002, p. 33). Plus récemment, selon Statistique Canada, la hausse de la productivité dans les entreprises en 2001 s’établissait à 1,2 % au Canada et à 1,9 % aux États-Unis. Selon Alan Toulin, journaliste au National Post, l’écart de productivité entre les deux pays voisins se creuse : «Hier, Statistique Canada rapportait que la productivité au Canada a baissé de 0,2 % pendant le premier trimestre de 2001, soit la première baisse annuelle depuis 1996. Durant la même période, les États-Unis ont enregistré une croissance de la productivité de 2,7 %, en dépit du ralentissement économique observé dans les deux pays. "Nous ne sommes pas en train de réduire l’écart avec les États-Unis; en fait, l’écart continue de s’élargir", a déclaré Tel Carmichael, économiste en chef pour le Canada à la firme de courtage J.P. Morgan. […] Les entreprises américaines ont investi massivement dans l’automatisation et les technologies de l’information qui donnent du tonus à la productivité même dans une période de ralentissement économique. Les entreprises canadiennes ont aussi investi dans les technologies qui améliorent l’efficacité du travail, mais pas dans la même proportion. […] La croissance de la productivité au Canada a présenté un ralentissement depuis le deuxième trimestre de 2000 alors qu’il avait atteint un sommet à 2,1 %. La croissance de la productivité aux États-Unis a toujours été supérieure au double de celle du Canada depuis la fin des années 1990» (www.tc.ca/pol/en/anre2000/tc00ghe.htm, traduction libre).

[ 2] Nous avons utilisé à cette fin un ordinateur portatif muni d’un Pentium 3 à 900 MHz et le progiciel commercial LINGO 7. Les modèles mathématiques incorporés dans LINGO 7, qui sont robustes et faciles à utiliser, ne sont pas les plus rapides, mais nous voulions seulement donner une idée de l’évolution des temps de calcul. Les données numériques des exemples traités ont été obtenues par simulation, en utilisant des lois uniformes [0; 1000] pour les coefficients cij.

[ 3] Par exemple, Pc Miler ou Rand McNally.

[ 4] Il est possible de construire des modèles scientifiques qui tiennent compte des fenêtres de temps, mais ces modèles sont plus complexes et n’entrent pas dans le cadre du problème classique du voyageur de commerce.

Résumé

Les gestionnaires du secteur du transport font régulièrement face à des problèmes de répartition de cueillettes, d’élaboration d’horaires ou d’itinéraires. Par exemple, un répartiteur doit déterminer quels colis un camion donné ira chercher, dans quel ordre il les cueillera et quels chemins il empruntera. Le coût du service rendu dépend de façon cruciale de ces décisions. L’objectif du présent article est de présenter des outils scientifiques qui permettent d’obtenir rapidement des solutions très efficientes. Cette approche scientifique est comparée à des méthodes intuitives utilisées couramment dans le secteur du transport et les gains financiers – et autres – que permet l’approche scientifique sont évalués. Les outils quantitatifs décrits dans cet article ont un champ d’application qui déborde largement le transport interurbain par camion. Ce secteur a été retenu pour illustrer de façon concrète les gains de productivité offerts aux gestionnaires par la recherche opérationnelle.

PLAN DE L'ARTICLE

• La répartition de charges entre des camions
• L’élaboration d’horaires
• Le problème du voyageur de commerce : la cueillette de colis par un camion
• Conclusion
• Annexe

Yves Nobert et al. « Le secteur du transport interurbain et la recherche opérationnelle : une synergie méconnue à exploiter », Gestion 2/2002 (Vol. 27), p. 38-45.
URL : www.cairn.info/revue-gestion-2002-2-page-38.htm.
DOI : 10.3917/riges.272.0038.