Problemes de gestion de flottes de vehicules en tempes reel (French text).
详细信息
文摘
Cette thèse porte sur le problème de répartition d'une flotte de véhicules en temps réel. Dans ces problèmes, il s'agit d'affecter des requêtes qui arrivent en temps réel à une flotte de véhicules en mouvement. Ce processus implique aussi la construction simultanée d'un ensemble de routes planifiées qui satisfont la demande, tout en respectant certaines contraintes.;Que l'on soit intéressé par le transport de biens ou de personnes, un grand défi à l'heure actuelle est d'élaborer des approches de résolution rapides mais efficaces dans un environnement qui évolue dans le temps. Notre thèse s'oriente vers ce nouvel axe de recherche qui est en pleine expansion grace aux progrès technologiques récents (p.e. positionnement par satellite, télé-détection, etc…). Nous nous attardons sur trois problématiques rencontrées dans les problèmes de gestion de flotte en temps réel et nous proposons des stratégies de résolution pour ces problématiques.;Les principales contributions de cette thèse se résument comme suit. Dans un premier temps, nous présentons une revue et une synthèse de la littérature consacrée aux problèmes de répartition de véhicules en temps réel. Nous dressons un inventaire non exhaustif des contextes d'application les plus répandus. Par la suite, nous classifions ces différents groupes de problèmes en nous basant sur une taxinomie établie au préalable. Nous discutons également des méthodologies générales adoptées pour traiter l'aspect dynamique de ces problèmes et nous dégageons quelques avenues de recherche qu'il serait pertinent d'approfondir dans le cadre de travaux futurs.;Dans le premier article, nous présentons une vision plus large du concept de la diversion. Nous examinons également différentes fa?ons d'intégrer ce concept à des algorithmes qui ne sont pas initialement con?us pour en tenir compte. Finalement, nous évaluons les bénéfices de son utilisation.;Dans le second article, nous proposons et analysons un modèle basé sur des temps de parcours variables dans le temps qui s'applique aussi bien dans un contexte statique que dans un contexte dynamique. Ensuite, nous comparons le modèle proposé à un modèle où les temps de parcours sont constants.;Dans le troisième article, nous proposons une stratégie qui exploite une anticipation des demandes futures afin d'améliorer la qualité des solutions obtenues. En particulier, la stratégie proposée introduit des demandes fictives (représentant des requêtes anticipées) dans les routes des véhicules afin d'assurer une bonne couverture territoriale. Nous évaluons enfin les bénéfices d'une telle stratégie pour différents scénarios d'opérations.;Les différentes problématiques étudiées sont abordées en incorporant les stratégies proposées au sein de méthodes heuristiques basées sur la recherche avec tabous. Afin de faire face aux pressions temporelles inhérentes à un contexte dynamique, des implantations parallèles sont réalisées afin d'accélérer les temps de réponse. Enfin, des tests numériques sont réalisés à l'aide de simulations qui s'inspirent de situations réelles observées dans les systèmes de courrier rapide. Les résultats numériques confirment la pertinence des différentes stratégies proposées.