# Algorithm for Trainyard Marshall optimization problem

The problem I am trying to solve is the 2014 RAS problem. The link is the following The problem

Trains come to the humpyard where each compartment of a train gets humped or disassembled and then each compartment is assigned to a track of classification bowl. The classification bowl is a set of parallel tracks. Each compartment from the incoming trains has a specific destination which is preassigned. Each outbound train have a departure time and some specified destinations where it will visit. When a outbound train leaves, the train takes available compartments from the classification bowl. The outbound trains have to be sorted by the destination order, so that when it reaches a destination the compartments can be disassembled from the outbound train with minimal effort. There are several restrictions such as, length of the tracks in classification bowl is limited, only one train can be humped at a time, the outbound train preparation can be started at a certain time etc. The aim is to minimize the total time taken for this whole process to finish.

So this problem was previously approached, and solved with a certain manner. Here is a link of the research which won the prize that year. The Approach

Now I was wondering if this problem can be solved heuristically or by using certain Local Search idea. I thought of a vague process. First we divide the whole process by 2/3 hour segments. We consider random assignment of the compartments of trains which arrive in that time segment. Then we do a local search procedure to find a good solution. Then we depart trains and remove the compartments from classification track which departed. To notice certain properties of a compartment in the classification track. Each compartment must follow the insertion sequence i.e. if compartment x is disassembled before compartment y in humpyard, then compartment y cannot appear before compartment x in the classification track. Also, the compartments in the classification track should follow the outbound train sequence and destination order. So we try to do a neighborhood search which minimize number of violations. For the neighborhood we can consider swapping two compartments, and/or taking one compartment and inserting in a random space. But there are certain flaws in this approach, I can feel it, but can't find a way out. Also I think this neighborhood search will take a lot of time. We can implement tabu search if we get the basics done, but the basics are really hard. The main reason being there are so many constrains. Can anyone point me in the right direction?

• My team came in third at that competition, and we did some random search to tune the parameters of a greedy decision heuristic (e.g. use the current state of the yarn and future upcoming trains to determine where to shunt the trains). A major challenge of this competition was that the input data is huge: it contains 40.000 traincars or so. Evaluating the costs of a solution was typically quite expensive. So without any special tricks, local search will probably be too slow. The winning team from Denmark mostly focused on optimizing the outbound trains, as that is the main bottleneck. – Paul Bouman Jun 22 '20 at 20:21
• @PaulBouman well can we connect somewhere. I want to know your approach. – Rio Jun 23 '20 at 8:01