999 resultados para Chemin plus court élémentaire avec contraintes de ressources
Resumo:
Cette thse porte sur les problmes de tournes de vhicules avec fentres de temps o un gain est associ chaque client et o l'objectif est de maximiser la somme des gains recueillis moins les cots de transport. De plus, un mme vhicule peut effectuer plusieurs tournes durant l'horizon de planification. Ce problme a t relativement peu tudi en dpit de son importance en pratique. Par exemple, dans le domaine de la livraison de denres prissables, plusieurs tournes de courte dure doivent tre combines afin de former des journes compltes de travail. Nous croyons que ce type de problme aura une importance de plus en plus grande dans le futur avec l'avnement du commerce lectronique, comme les piceries lectroniques, o les clients peuvent commander des produits par internet pour la livraison domicile. Dans le premier chapitre de cette thse, nous prsentons d'abord une revue de la littrature consacre aux problmes de tournes de vhicules avec gains ainsi qu'aux problmes permettant une rutilisation des vhicules. Nous prsentons les mthodologies gnrales adoptes pour les rsoudre, soit les mthodes exactes, les mthodes heuristiques et les mta-heuristiques. Nous discutons enfin des problmes de tournes dynamiques o certaines donnes sur le problme ne sont pas connues l'avance. Dans le second chapitre, nous dcrivons un algorithme exact pour rsoudre un problme de tournes avec fentres de temps et rutilisation de vhicules o l'objectif premier est de maximiser le nombre de clients desservis. Pour ce faire, le problme est modlis comme un problme de tournes avec gains. L'algorithme exact est bas sur une mthode de gnration de colonnes couple avec un algorithme de plus court chemin élémentaire avec contraintes de ressources. Pour rsoudre des instances de taille raliste dans des temps de calcul raisonnables, une approche de rsolution de nature heuristique est requise. Le troisime chapitre propose donc une mthode de recherche adaptative grand voisinage qui exploite les diffrents niveaux hirarchiques du problme (soit les journes compltes de travail des vhicules, les routes qui composent ces journes et les clients qui composent les routes). Dans le quatrime chapitre, qui traite du cas dynamique, une stratgie d'acceptation et de refus des nouvelles requtes de service est propose, base sur une anticipation des requtes venir. L'approche repose sur la gnration de scnarios pour diffrentes ralisations possibles des requtes futures. Le cot d'opportunit de servir une nouvelle requte est bas sur une valuation des scnarios avec et sans cette nouvelle requte. Enfin, le dernier chapitre rsume les contributions de cette thse et propose quelques avenues de recherche future.
Resumo:
De nombreux problmes pratiques qui se posent dans dans le domaine de la logistique, peuvent tre modliss comme des problmes de tournes de vhicules. De faon gnrale, cette famille de problmes implique la conception de routes, dbutant et se terminant un dpt, qui sont utilises pour distribuer des biens un nombre de clients gographiquement dispers dans un contexte o les cots associs aux routes sont minimiss. Selon le type de problme, un ou plusieurs dpts peuvent-tre prsents. Les problmes de tournes de vhicules sont parmi les problmes combinatoires les plus difficiles rsoudre. Dans cette thse, nous tudions un problme doptimisation combinatoire, appartenant aux classes des problmes de tournes de vhicules, qui est lie au contexte des rseaux de transport. Nous introduisons un nouveau problme qui est principalement inspir des activits de collecte de lait des fermes de production, et de la redistribution du produit collect aux usines de transformation, pour la province de Qubec. Deux variantes de ce problme sont considres. La premire, vise la conception dun plan tactique de routage pour le problme de la collecte-redistribution de lait sur un horizon donn, en supposant que le niveau de la production au cours de lhorizon est fix. La deuxime variante, vise fournir un plan plus prcis en tenant compte de la variation potentielle de niveau de production pouvant survenir au cours de lhorizon considr. Dans la premire partie de cette thse, nous dcrivons un algorithme exact pour la premire variante du problme qui se caractrise par la prsence de fentres de temps, plusieurs dpts, et une flotte htrogne de vhicules, et dont lobjectif est de minimiser le cot de routage. cette fin, le problme est modlis comme un problme multi-attributs de tournes de vhicules. Lalgorithme exact est bas sur la gnration de colonnes impliquant un algorithme de plus court chemin élémentaire avec contraintes de ressources. Dans la deuxime partie, nous concevons un algorithme exact pour rsoudre la deuxime variante du problme. cette fin, le problme est modlis comme un problme de tournes de vhicules multi-priodes prenant en compte explicitement les variations potentielles du niveau de production sur un horizon donn. De nouvelles stratgies sont proposes pour rsoudre le problme de plus court chemin élémentaire avec contraintes de ressources, impliquant dans ce cas une structure particulire tant donn la caractristique multi-priodes du problme gnral. Pour rsoudre des instances de taille raliste dans des temps de calcul raisonnables, une approche de rsolution de nature heuristique est requise. La troisime partie propose un algorithme de recherche adaptative grands voisinages o de nombreuses nouvelles stratgies dexploration et dexploitation sont proposes pour amliorer la performances de lalgorithme propos en termes de la qualit de la solution obtenue et du temps de calcul ncessaire.
Resumo:
Mmoire numris par la Direction des bibliothques de l'Universit de Montral.
Resumo:
Mmoire numris par la Direction des bibliothques de l'Universit de Montral.
Resumo:
Cette these sinteresse aux problemes de tournees de vehicules ou lon retrouve des contraintes de chargement ayant un impact sur les sequences de livraisons permises. Plus particulierement, les items places dans lespace de chargement dun vehicule doivent etre directement accessibles lors de leur livraison sans quil soit necessaire de deplacer dautres items. Ces problemes sont rencontres dans plusieurs entreprises de transport qui livrent de gros objets (meubles, electromenagers). Le premier article de cette these porte sur une methode exacte pour un probleme de confection dune seule tournee ou un vehicule, dont laire de chargement est divisee en un certain nombre de piles, doit effectuer des cueillettes et des livraisons respectant une contrainte de type dernier entre, premier sorti. Lors dune collecte, les items recueillis doivent necessairement etre deposes sur le dessus de lune des piles. Par ailleurs, lors dune livraison, les items doivent necessairement se trouver sur le dessus de lune des piles. Une methode de separation et evaluation avec plans secants est proposee pour resoudre ce probleme. Le second article presente une methode de resolution exacte, egalement de type separation et evaluation avec plans secants, pour un probleme de tournees de vehicules avec chargement ditems rectangulaires en deux dimensions. Laire de chargement des vehicules correspond aussi a un espace rectangulaire avec une orientation, puisque les items doivent etre charges et decharges par lun des cotes. Une contrainte impose que les items dun client soient directement accessibles au moment de leur livraison. Le dernier article aborde une probleme de tournees de vehicules avec chargement ditems rectangulaires, mais ou les dimensions de certains items ne sont pas connus avec certitude lors de la planification des tournees. Il est toutefois possible dassocier une distribution de probabilites discrete sur les dimensions possibles de ces items. Le probleme est resolu de maniere exacte avec la methode L-Shape en nombres entiers.
Resumo:
Rapport de recherche
Resumo:
Thse numrise par la Division de la gestion de documents et des archives de l'Universit de Montral
Resumo:
Some plates signed by Ferdinand Delamonce.
Resumo:
Mode of access: Internet.
