Génération de mises combinatoires dans les enchères de transport en univers incertain

Pour les enchères combinatoires de transport, construire la bonne mise à soumettre dans l'enchère est très important. Mise à part l'obligation de se conformer aux préférences et règlements de l'enchère, un transporteur doit d'un côté augmenter ses chances de gagner et de l'autre côté prendre en considération ses engagements actuels. Les travaux effectués dans la littérature sur ce type de problèmes comprennent une variété de solutions proposées. Quelques auteurs proposent de construire une mise en donnant une approximation de la probabilité de gagner dans l'enchère. D'autres auteurs proposent de générer une mise de façon à prendre en considération la synergie qui peut naître entre les composantes de cette mise elles-mêmes et les engagements actuels du transporteur. Cependant, aucun auteur n'a proposé une méthode efficace qui construit simultanément deux mises disjointes à déposer dans l'enchère tout en prenant en compte la probabilité de gagner : l'une des deux mises, les deux mises ou aucune de celles-ci. Contrairement aux approches établies dans la littérature, où la construction des deux mises disjointes se fait sur plusieurs étapes (sélectionner les contrats convenables puis les séparer en deux mises), notre approche permet d'effectuer ces mêmes étapes simultanément. Ceci permet d'avoir la possibilité de revoir les contrats à inclure dans les mises et les routes à opérer pour chacun des cas mentionnés ci-haut. Nous avons élaboré trois méthodes de résolution. La première méthode découle de la littérature et repose sur des modèles et techniques existants. Nous avons alors considéré que les résultats obtenus par cette méthode constituent un point de référence auquel on peut comparer les résultats des méthodes 2 et 3. Ces dernières offrent des solutions meilleures que la méthode 1 et reposent sur des principes assez différents. La méthode 2 s'exécute sur plusieurs étapes et donne par conséquent une solution approchée pour notre problème. Cependant, La méthode 3 avec son caractère intégré trouve la solution optimale du problème. En premier lieu, nous avons comparé les résultats des trois méthodes moyennant un algorithme de résolution exact qui repose sur un principe de Branch-and-Price. Cet algorithme a permis de résoudre des instances comprenant jusqu'à 15 villes et 133 contrats. En deuxième lieu, nous avons introduit une heuristique pour la méthode 3 qui s'est avérée de bonne qualité. Les performances de cette heuristique ont été évaluées en comparaison par rapport aux méthodes 2 et 3. Nous sommes parvenus à trouver des solutions meilleures que la méthode 2 mais dont le temps de calcul est inclus entre celui des méthodes 2 et 3. Malgré cet inconvénient, ce temps de calcul reste réduit et a été limité à une heure de résolution. De plus, Nous sommes parvenus à résoudre des instances tels que le nombre de villes et de contrats disponibles est de 17 et 195 respectivement.