Proposition de th
Forum 'Emplois' - Sujet créé le 2005-05-09
Titre : Problèmes de tournées sur arcs avec fenêtres horaires et préemptions
Laboratoire : ISTIT( FRE CNRS 2732) – Equipe OSI
Etablissement: Université de Technologie de Troyes (UTT)
Encadrement : Nacima LABADI (MDC) et Christian PRINS (PR)
1. Description du sujet de thèse
Les problèmes de tournées de véhicules se situent au coeur de la problématique très actuelle de la réduction des coûts de la logistique et du transport. Il s’agit d'effectuer à moindre coût, avec des véhicules, un ensemble de tâches dispersées sur un réseau routier. Ces tâches peuvent correspondre à des lieux ponctuels appelés nœuds (livrer du fioul à un client) ou s'étendre sur un segment de rue ou route appelé arc (saler une rue en cas de verglas).
Ces problèmes très combinatoires ont de nombreuses applications : logistique de distribution (pour les tournées sur nœuds), collecte de déchets, salage ou sablage de routes, nettoyage de la voirie, fauchage de bas-côtés, relevé de compteurs etc (pour les tournées sur arcs). Depuis 20 ans, d'assez nombreux articles ont été publiés pour les problèmes de tournées sur nœuds mais les problèmes sur arcs ont été relativement peu étudiés en comparaison. La thèse vise à combler cette lacune en étudiant des problèmes de tournées sur arcs avec deux complications importantes : les contraintes temporelles et la préemption des tâches (splitting).
Les contraintes temporelles sont en général des fenêtres de temps pendant lesquelles une tâche doit ou ne doit pas être effectuée. Ainsi, dans de nombreuses grandes villes, la collecte de déchets est interdite le matin à l'heure de pointe car les camions en collecte se déplacent trop lentement. Il s'agit alors d'interdictions de traitement mais pas d'accès : les camions peuvent quand même emprunter ces rues pour rejoindre leur secteur à traiter. Mais une rue peut être temporairement bloquée à cause d'un marché ou de travaux. Il s'agit dans ce cas d'une interdiction d'accès, qui implique une interdiction de traitement : un camion de collecte de déchets ne pourra ni traiter cette rue ni simplement y passer pour aller traiter une autre rue.
Dans la littérature sur les tournées sur nœuds, les fenêtres horaires ne définissent que des interdictions de traitement, par exemple une fenêtre de livraison allouée à un livreur par un hypermarché : le magasin est placé sur un nœud du réseau (village, carrefour) mais la fenêtre horaire ne bloque pas le trafic de passage. Dans les tournées sur arcs, les fenêtres définissent souvent des interdictions d'accès, empêchant le trafic de passage. Ceci soulève une difficulté majeure : les plus courts chemins pour aller d'un point à un autre changent selon l'heure.
La plupart des articles publiés supposent des tâches non-préemptibles : il est vrai qu'aucun client n'aime être dérangé deux fois dans une même journée pour qu'on lui livre du fioul. Par contre, la préemption des tâches est possible, et même souhaitable, dans les problèmes sur arcs, par exemple la collecte partielle des déchets d'un long boulevard. La préemption apporte dans ce cas de la flexibilité, par exemple en répartissant une tâche sur plusieurs véhicules.
Le but de cette thèse est de développer des modèles et des méthodes de calcul pour résoudre ce type de problèmes. Le candidat retenu aura aussi à proposer des jeux d’essais pertinents pour valider les résultats obtenus.
Le candidat doit avoir des connaissances solides des outils et techniques d’optimisation et avoir des aptitudes dans l’analyse d’algorithmes et programmation. Si vous êtes intéressé, envoyez un CV, vos résultats dans la partie théorique du Master ainsi qu’une lettre de motivation aux coordonnées ci-dessous.
Financement : oui.
Contacts : Christian PRINS et Nacima LABADI
03 25 71 80 26
03 25 71 56 41
christian.prins@utt.fr, nacima.labadi@utt.fr.
Adresse : Université de Technologie de Troyes
ISTIT-OSI, 12 rue Marie Curie, BP 2060
10010 Troyes Cedex
Laboratoire : ISTIT( FRE CNRS 2732) – Equipe OSI
Etablissement: Université de Technologie de Troyes (UTT)
Encadrement : Nacima LABADI (MDC) et Christian PRINS (PR)
1. Description du sujet de thèse
Les problèmes de tournées de véhicules se situent au coeur de la problématique très actuelle de la réduction des coûts de la logistique et du transport. Il s’agit d'effectuer à moindre coût, avec des véhicules, un ensemble de tâches dispersées sur un réseau routier. Ces tâches peuvent correspondre à des lieux ponctuels appelés nœuds (livrer du fioul à un client) ou s'étendre sur un segment de rue ou route appelé arc (saler une rue en cas de verglas).
Ces problèmes très combinatoires ont de nombreuses applications : logistique de distribution (pour les tournées sur nœuds), collecte de déchets, salage ou sablage de routes, nettoyage de la voirie, fauchage de bas-côtés, relevé de compteurs etc (pour les tournées sur arcs). Depuis 20 ans, d'assez nombreux articles ont été publiés pour les problèmes de tournées sur nœuds mais les problèmes sur arcs ont été relativement peu étudiés en comparaison. La thèse vise à combler cette lacune en étudiant des problèmes de tournées sur arcs avec deux complications importantes : les contraintes temporelles et la préemption des tâches (splitting).
Les contraintes temporelles sont en général des fenêtres de temps pendant lesquelles une tâche doit ou ne doit pas être effectuée. Ainsi, dans de nombreuses grandes villes, la collecte de déchets est interdite le matin à l'heure de pointe car les camions en collecte se déplacent trop lentement. Il s'agit alors d'interdictions de traitement mais pas d'accès : les camions peuvent quand même emprunter ces rues pour rejoindre leur secteur à traiter. Mais une rue peut être temporairement bloquée à cause d'un marché ou de travaux. Il s'agit dans ce cas d'une interdiction d'accès, qui implique une interdiction de traitement : un camion de collecte de déchets ne pourra ni traiter cette rue ni simplement y passer pour aller traiter une autre rue.
Dans la littérature sur les tournées sur nœuds, les fenêtres horaires ne définissent que des interdictions de traitement, par exemple une fenêtre de livraison allouée à un livreur par un hypermarché : le magasin est placé sur un nœud du réseau (village, carrefour) mais la fenêtre horaire ne bloque pas le trafic de passage. Dans les tournées sur arcs, les fenêtres définissent souvent des interdictions d'accès, empêchant le trafic de passage. Ceci soulève une difficulté majeure : les plus courts chemins pour aller d'un point à un autre changent selon l'heure.
La plupart des articles publiés supposent des tâches non-préemptibles : il est vrai qu'aucun client n'aime être dérangé deux fois dans une même journée pour qu'on lui livre du fioul. Par contre, la préemption des tâches est possible, et même souhaitable, dans les problèmes sur arcs, par exemple la collecte partielle des déchets d'un long boulevard. La préemption apporte dans ce cas de la flexibilité, par exemple en répartissant une tâche sur plusieurs véhicules.
Le but de cette thèse est de développer des modèles et des méthodes de calcul pour résoudre ce type de problèmes. Le candidat retenu aura aussi à proposer des jeux d’essais pertinents pour valider les résultats obtenus.
Le candidat doit avoir des connaissances solides des outils et techniques d’optimisation et avoir des aptitudes dans l’analyse d’algorithmes et programmation. Si vous êtes intéressé, envoyez un CV, vos résultats dans la partie théorique du Master ainsi qu’une lettre de motivation aux coordonnées ci-dessous.
Financement : oui.
Contacts : Christian PRINS et Nacima LABADI
03 25 71 80 26
03 25 71 56 41
christian.prins@utt.fr, nacima.labadi@utt.fr.
Adresse : Université de Technologie de Troyes
ISTIT-OSI, 12 rue Marie Curie, BP 2060
10010 Troyes Cedex