We　introduce　a　hard　practical　optimization　problem,　the　ship　traffic　control　problem　(STCP).　We　study　it　at　the　Kiel　Canal,　which　is　the　most　frequented　artificial　waterway　in　the　world.　The　canal　is　operated　bidirectionally,　but　large　ships　can　pass　each　other　only　in　sidings.　Decisions　must　be　made　about　who　is　waiting　for　whom,　where,　and　for　how　long,　subject　to　a　multitude　of　operational　constraints.　The　objective　is　to　minimize　the　total　waiting　times　of　all　ships.　This　problem　generalizes　train　scheduling　on　a　single-track　network.　We　integrate　algorithmic　ideas　from　collision-free　routing　of　automated　guided　vehicles.　This　leads　to　a　unified　view　of　scheduling　and　dynamic　routing　that　may　serve　as　a　prototype　for　scheduling　bidirectional　traffic　with　passing　conflicts.　We　implement　a　traffic　control　tool　that　uses　our　combinatorial　algorithms　and　perform　a　computational　study　on　traffic　data　from　the　Kiel　Canal.　Our　tool　produces　schedules　that　significantly　improve　over　manual　planning　and　were　approved　by　expert　planners.　As　traffic　volume　and　vessel　sizes　are　projected　to　significantly　increase,　the　canal　is　planned　to　be　enlarged　in　a　huge　project.　Our　tool　was　used　to　select　from　a　variety　of　enlargement　options.　The　enormous　level　of　detail　in　our　model　ensured　that　the　chosen　construction　scenario　actually　constitutes　a　remedy　to　the　impending　inoperability　of　the　canal.