Etat de l’art des méthodes de des problèmes de transport

Les activités de transport de personnes et de marchandises posent plusieurs problématiques à tous les niveaux décisionnels (i.e. stratégique, tactique et opérationnel). Que cela soit pour la construction de réseaux logistiques, leur gestion et leur organisation, l’optimisation de la circulation des flux (personnes et marchandises), l’optimisation de la circulation des véhicules (planification des tournées et optimisation des parcours), etc. La majeure partie des problématiques relatives à la chaîne logistique et au transport, sont des problèmes d’optimisation combinatoire et sont classées dans la catégorie des problèmes NP-difficile (Gupta & Könemann, 2011). Une grande variété de méthodes de résolution exactes et approchées ont été proposées pour résoudre de tels problèmes. Les solveurs sont souvent en mesure de résoudre les petites et moyennes instances de manière optimale. Cependant, des modèles riches ou des instances de grande taille, ne peuvent être résolus de manière optimale, même par les solveurs les plus performants, dans des délais acceptables. Ainsi, il est nécessaire de développer des algorithmes pour une résolution approchée (Alumur , et al., 2015). Dans ce travail de recherche, nous nous intéressons à la conception et à la modélisation d’une nouvelle solution de transport ferroviaire de marchandises en milieu urbain. Dans ce cadre, plusieurs problèmes d’optimisation combinatoire sont identifiés. La simulation à évènements discrets, en utilisant le logiciel ARENA, est proposée dans le but de comprendre le comportement de cette solution de transport et d’étudier sa dynamique dans le temps. Le modèle de simulation nous permet aussi, de reproduire les perturbations liées à la mise en exploitation d’une telle solution de transport.

Problèmes classiques de la littérature liés à la logistique urbaine

– Le problème de tournée de véhicules (Dantzig & Ramser, 1959) : cette classe de problèmes classiques en optimisation combinatoire, consiste à déterminer les tournées optimales de plusieurs véhicules, dans le but de livrer plusieurs clients (à noter que lorsqu’il n’y a qu’un seul véhicule, ce problème se réduit au problème du voyageur de commerce). Plusieurs variantes de problèmes de tournées de véhicules existent. A titre d’exemple : 1- avec fenêtre de temps, où il s’agit de livrer chaque client, sur un intervalle de temps réduit, 2- avec collecte et livraison, où il s’agit pour les véhicules de transport, de procéder à des collectes de marchandises, en plus des livraisons, 3- contraintes de capacité, où les véhicules ont une capacité limité en termes de poids / volume… – Le problème d’affectation (Schrijver, 2005) : c’est l’un des premiers problèmes d’optimisation combinatoire. Il a été étudié par Gaspard Monge dès 1784. Ce problème est le plus souvent assimilé au problème de transport décrit précédemment. La description classique de ce problème consiste à déterminer l’affectation de tâches à des agents, sachant que chaque affectation tâche-agent a un coût, l’objectif étant de minimiser le coût total des affectations. Appliqué au transport, il s’agira de déterminer pour chaque commande (produits ou marchandises), le véhicule qui va la transporter. Une variante plus complexe de ce type de problème existe, il s’agit du problème d’affectation généralisée, qui introduit des contraintes supplémentaires. Ce problème sera décrit plus en détail dans la suite de ce chapitre.

– Le problème de bin packing (Johnson & Garey, 1985) : ce problème consiste à déterminer le meilleur placement d’objets, à l’intérieur de plusieurs contenants, dont l’objectif est la minimisation du nombre de contenants pour tous les objets. Appliqué au transport, ce problème se traduit par l’optimisation du chargement de véhicules de transport (ex : camions) ou containers (à transporter dans des bateaux ou trains), dans le but de minimiser le nombre de véhicules à utiliser pour transporter tous le produits. Des contraintes sur le volume du contenant et le poids maximum supporté par les véhicules sont à considérer.