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.

Abstract

For transportation combinatorial auctions, building the perfect bid to submit in the auction is very important. In fact, this bid can help the carrier gain more profit and thus demand less price for it which increases his chances to win in the auction. To do that, a carrier must not only respect the auction restrictions but also take into account the nature of its transportation activity. The research done until today regarding this subject includes a diversity of proposed solutions. Some researchers propose a solution where they give an approximation of the probability to win in the auction. Others propose to build the bid taking into account the synergy that can occur between both the components of the bid itself and the current commitments of the carrier. However, it is the first time someone carries a research on how to build efficiently two disjoint bids taking into account the probability of the following outcomes: win one of the bids, win both of the bids and lose in the auction. This last solution is exactly how we approached the construction bid problem. Using it, the carrier will have the possibility to submit two bids to the auction and also to review the bid components and the routes to operate for each one of the probabilistic outcomes mentioned above. The advantage for such an approach in respect with what has been done until today when it comes to building two disjoint bids is that the carrier can now choose the best contracts to include in the bids and construct the routes for these bids simultaneously and not through multiple steps that prevent the optimality. We have developed three methods for our main objective. Method 1 derives from the literature and uses mathematical models and techniques that already exist in the literature. For this reason, we considered this method as a reference to which we will compare the other 2 methods to confirm the gain of profit that our approach ensures. Methods 2 and 3 yield eventually better profit to the carrier but use quite different principles. Method 2 is based on an existing mathematical model and is run on a set of steps. However, method 3 is run on a single integrated step and gives the optimal solution of the problem. As a first step, we have compared the results yielded by the three methods using an exact algorithm which is based on a branch-and-price principle. We were able to solve instances with a number of customers and contracts reaching 15 and 133 respectively. Then, we introduced a heuristic for method 3. We have compared its solutions to the ones given by methods 2 and 3 when solved by the exact algorithm. The heuristic spends less CPU time that method 3, greater CPU time than method 2 and a profit situated between those of methode 2 and 3 for the majority of instances. Although our heuristic finds its solutions in a greater time than method 2 for few of the instances tested, we have set a limit of 1 hour when solving it, which is far from being considered as a long CPU time. Besides, we were able to solve instances with a number of customers and contracts reaching 17 and 195 contracts respectively.