Le problème du postier chinois cumulatif

Le sujet de cette thèse est le problème du postier chinois cumulatif (PPCC). Dans ce problème, nous considérons l'importance du moment où une arête est traitée complètement. Cette façon de procéder introduit un caractère cumulatif et dynamique dans le coût réel des arêtes, ce qui a pour effet de changer la structure du problème du postier chinois. Nous démontrons que ce problème est fortement NP-difficile et réductible à une version du problème de voyageur de commerce cumulatif. Ce problème est, à notre connaissance, nouveau. Nous continuons ici l'étude entreprise dans notre mémoire de maîtrise. Notre but dans cette thèse est de résoudre exactement ce problème à l'aide des outils de la programmation linéaire en nombres entiers. Notre contribution est de plusieurs ordres. Premièrement, nous développons une vingtaine de modèles différents. Dans cette thèse, nous étudions les huit meilleurs et les comparons aussi bien empiriquement que théoriquement entre eux et démontrons toutes les relations de dominance entre eux. L'aboutissement de nos recherches est le modèle L8. Deuxièmement, nous résolvons ce modèle L8 à l'aide d'un algorithme de séparation et évaluation progressive (Branch and Cut - algorithme BC1). Nous développons plusieurs outils dont nous présentons ici trois branchements, sept pré-traitements, six familles de coupes dont trois que nous généralisons. Ces outils nous permettent déjà de battre le solveur CPLEX par un facteur de 3 à 58 sur nos graphes de référence. Troisièmement, nous développons une meilleure variante du modèle L8 : le modèle L8+ et utilisons une approche avec génération de colonnes (Branch, Price and Cut – algorithme BPC1). Dans la foulée, nous développons cinq familles de coupes et nous généralisons quatre d'entre-elles. Cette nouvelle approche, plus rapide que la première d'un facteur de 2 à 4, nous permet d'être de 2 à 133 fois plus rapide que le solveur CPLEX en utilisant le modèle L8+ sur nos graphes de référence. Quatrièmement, nous améliorons notre approche de génération de colonnes (Branch, Price and Cut – algorithme BPC2) avec une évaluation implicite du dual. Les plus grandes instances du PPCC que nous arrivons à résoudre dans un délai maximal d'une heure comprennent des graphes de 11 sommets et/ou de 55 arêtes, ce qui correspond approximativement à des instances du problème du voyageur de commerce cumulatif à 110 sommets. Mots clefs Tournées sur les arcs, fonction cumulative, problème du postier chinois cumulatif.

Abstract

The subject of this Ph.D. thesis is the Cumulative Chinese Postman Problem (CCPP). We focus on the delay of the service of each arc. This introduces a cumulative and dynamic aspect in the objective function therefore changing the structure of the Chinese Postman Problem. We prove that this problem is strongly NP-hard and reducible to a version of the Cumulative Travelling Salesman Problem. This problem is, to our knowledge, entirely new. The study of this problem was initiated in our master thesis. Our main goal in this thesis is to solve this problem exactly with the help of the tools of linear integer programming. Our contribution is manifold. First, we develop twenty different models. However, in this thesis, we only discuss and compare theoretically and experimentally the best eight models. We prove all dominance relations among them. Model L8 stands out as the best model. Secondly, we solve this model L8 with a Branch and Cut (algorithm BC1). Throughout our study, we develop several tools among which three branching rules, seven presolving algorithms, six families of cuts (three of them generalized). These tools alone allow us to solve the problem faster than CPLEX by a factor of 3 to 58 on our test graphs. Thirdly, we develop an improved model L8+ and use a column generation approach - a Branch, Price and Cut (algorithm BPC1). We also develop five new families of cuts (four of them generalized). This new approach is faster than the previous one by a factor of 2 to 4 and is faster than CPLEX with the new model L8+ by a factor of 2 to 133 on our test graphs. Fourthly, we improve our Branch, Price and Cut algorithm (algorithm BPC2) by using an implicit evaluation of the dual. The largest instances for which we are able to solve the CCPP in less than one hour include graphs with 11 nodes and/or 55 edges which correspond approximately to instances of the Cumulative Travelling Salesman Problem with 110 nodes.