Decomposing and Interactively Solving a High Dimensional Problem; Scheduling Trains on Shunting Yards

Abstract

Sometimes a complex combinatorial problem has easily identifiable subproblems for which methods are available. Often, strong interactions between these subproblems prevent us to use these methods in a straightforward way. In railway industry, finding a schedule for train service and shunting tasks is an example of such a problem with clearly identifiable, interacting subproblems: Trains with given length have to be parked on a track (BinPacking), a route to that track has to exist (Motion Planning), leaving trains need to be composed of multiple train units of arrived trains (SetCover) and service tasks have to be performed to trains (RCPSP). In practice, we often see that humans tend to split such a problem and solve it sequentially, e.g. they first solve the parking problem and then the routing problem. Often, solving such problems in a sequence enforces complex feedback loops. We present a method for decomposing the problem into subproblems such that algorithms for subproblems can be designed independently, without enforcing feedback loops. Subproblems will contain shared variables, for which they must cooperate to find a feasible assignment for the complete problem. Cooperation between subproblems is achieved by iteratively letting one of the subproblems propose a set of changes to a global assignment of variables, a single variable change is selected by letting all subproblems vote. Subproblems will be coordinated by a coordination algorithm to enforce progress.