Nous considérons un problème de routing de conteneurs dans un réseau maritime, où la prise en compte des contraintes de cabotage constitue un enjeu central. Nous proposons une modélisation du problème s'appuyant sur un graphe orienté représentant le réseau de services d'une compagnie maritime. La formulation du problème intègre les différentes situations de cabotage pouvant survenir au cours d'un routing. La structure du problème nous conduit à développer une méthode de résolution spécifique par génération de colonnes, capable d'intégrer finement ces contraintes. Les résultats numériques sur données réelles montrent que cette approche permet de traiter efficacement le problème tout en respectant strictement les règles de cabotage.