Une approche interdisciplinaire pour l’ordonnancement des transports

Une approche interdisciplinaire pour l’ordonnancement des transports

Systèmes d’aide à la décision pour l’ordonnancement des transports 

Problèmes de décision 

Dans la réalité des problèmes d’ordonnancement des transports, des décisions doivent constamment être prises pour trouver une solution qui satisfasse les requêtes des clients sans violer les contraintes du problème. La volonté d’automatiser à outrance les systèmes de décisions a souvent conduit à placer l’humain à la périphérie du système décisionnel. Cependant, la nécessite de modifier les solutions proposées par ces systèmes, de fa¸con à ce que les exigences qui ne peuvent pas être formalisées soient aussi satisfaites, mais aussi la nécessité de réagir rapidement face à l’imprévu, obligent à une participation de l’humain dans le processus de construction des solutions effectivement appliquées. Dans un tel contexte dynamique, il est souvent nécessaire de prendre des décisions dans des intervalles de temps très courts. Cette réactivité est en grande partie assurée par les planificateurs humains, dont les connaissances et le savoir-faire acquis au cours du temps ne peuvent être modélisés de manière formelle. Cela a conduit a concevoir une approche coopérative o`u les systèmes décisionnels évoluent vers les systèmes d’aide à la décision. Le but de ces derniers est d’assister le planificateur dans le processus de prise de décisions. Dans ce cadre, pour une conception efficace de ces systèmes d’aide à la décision, il est nécessaire d’identifier tout d’abord quelles sont les capacités et les manques de l’humain pour chacune des actions à réaliser pendant le processus de résolution du problème. Par exemple, l’humain est très compétent pour arriver à trouver un compromis entre différents critères. En revanche, il est très inefficace pour vérifier et maintenir un ensemble important de contraintes, tˆache o`u, au contraire, le système informatisé est performant. Ceci permet de concevoir des algorithmes et des mécanismes d’interaction davantage adaptés aux besoins du planificateur humain. 

L’ordonnancement des transports

 La problématique liée à l’ordonnancement des transports a été largement étudiée au cours des dernières décennies. Dans cette catégorie de problèmes, nous trouvons deux classes de problèmes qui ont beaucoup attiré l’attention des chercheurs : le problème de transport et le problème de tournées de véhicules. Le problème de transport (transportation problem) fut formulé pour la première fois par Hitchcock (1941). Ce problème consiste à minimiser le coˆut de transport total d’un plan d’expédition. Le problème est un cas particulier d’un problème de graphe (le problème de flot maximal à coˆut minimal dans un graphe orienté biparti). Il peut être résolu avec un algorithme de complexité polynomiale (voir par exemple Nemhauser and Wosley (1999); Lacomme et al. (2003)). Le problème de tournées de véhicules ou VRP (Vehicle Routing Problem) a été introduit par Dantzig and Ramser (1959). Le problème consiste à déterminer les itinéraires à suivre par une flotte de véhicules de transport (de biens, de passagers) de manière à satisfaire un ensemble de requêtes clients (livraisons, collecte, ramassage, …). Ce problème est une extension du problème du voyageur de commerce ou TSP (Travelling Salesman Problem) (Lawler et al., 1985; Gutin and Punnen, 2002). Il fait partie de la classe de problèmes NP-complets (Lenstra and Kan, 1981). Il n’existe pas d’algorithme de complexité polynomiale pour résoudre le problème. Toutefois, des méthodes issues de la Recherche Opérationnelle existent pour résoudre efficacement certaines des nombreuses variantes du VRP (Toth and Vigo, 2001; Cordeau et al., 2005; Barnhart and Laporte, 2007; Golden et al., 2008). Ces méthodes sont principalement de méta-heuristiques (recherche tabou, algorithmes génétiques, …) qui permettent de trouver des solutions de bonne qualité en un temps de calcul raisonnable. Dans les paragraphes suivantes, nous présentons plus profondément le problème de transport et le problème de tournées de véhicules. Ensuite, nous énumérons les caractéristiques et  particularités des différentes variantes du problème de tournées de véhicules. Finalement, nous présentons brièvement les systèmes d’aide à la décision pour l’ordonnancement des transports existant dans la littérature.

Définition du problème de transport 

Le problème de transport peut être décrit de la fa¸con suivante. Une quantité de produit uniforme est disponible en certains points appelés origines (par exemple dépˆots, ports, …). D’un autre cˆoté, une quantité de produit est demandée en d’autres points appelés destinations (par exemple clients, points de vente, …). Il s’agit d’envoyer les produits des origines aux destinations. Nous considérons qu’il existe toujours un chemin pour aller de chaque origine à chaque destination. Le coˆut de transport d’une unité de produit des origines vers les destinations est connu. L’objectif est de déterminer la distribution de produit qui permette de satisfaire la demande de chaque destination et de minimiser le coˆut total de transport. Nous supposons un ensemble de m origines et n destinations. Notons ai la quantité d’unités de produit disponible à l’origine i, et bj la quantité d’unités de produit demandé par la destination j. Le coˆut de transport d’une unité de produit depuis l’origine i vers la destination j est noté cij .