A Stockyard Planning Puzzle –
My name is David and for my master’s thesis in Quantitative Logistics and Operational Research, I have worked on optimising the processes in a port that handles dry bulk materials. In this port, raw materials such as coal and iron ore are brought into the port by vessel, moved into the stockyard, and finally used in a production process. First, a vessel is scheduled at a berth. At the berth, the vessel is unloaded by cranes after which it departs. Meanwhile, the unloaded material is transported by a conveyor belt to one of the pads, which are long inventory grounds on which the stockpiles can be stored. When it arrives at a pad, the stockpile is built by a stacker-reclaimer (big crane-like machines, which can ‘stack’ and ‘reclaim’ the stockpiles in its pad). Finally, when the production facility requests the stockpile, the pile is reclaimed, after which the raw material is transported to the production facility.
The situation of the port can be described by a mathematical formulation called the stockyard planning problem. The main challenge in the stockyard planning lays in the fact that the stockyard has limited capacity to store stockpiles. When a vessel arrives and is not able to unload its stockpiles as a result of the limited capacity, it has to wait and incurs demurrage cost. The goal of the stockyard planning problem is therefore to use the capacity of the yard as efficiently as possible to minimise demurrage costs over all vessels. Like we are laying a large jigsaw puzzle, each stockpile has to fit with one another to limit the total delay of all vessels.
A balance between speed and quality
To make the puzzle fit, we have to decide on a good puzzling strategy. Next to the strategy quality, planners also like to have a schedule within a foreseeable period of time. Therefore, the puzzling strategy also has to be speedy. Ideally, we balance speed and quality perfectly such the solution is both quick and optimal. To blend in the two together, I have chosen to create a construction heuristic which inserts each vessel and its stockpiles into the schedule. This heuristic not only creates a schedule within a fraction of a second, but is also constructed with the quality aspect in mind by laying the puzzle such that each stockpile is fitted as compactly as possible.
To further improve the quality of the solution, we are now left with two options. We could locally improve the puzzle by moving groups of stockpiles such that the vessel demurrage decreases. While this could be a good idea, it does not improve the collective fit of the puzzle and most importantly, it does not play into the speed of the construction heuristic. A better idea might be to use the order in which the construction heuristic is performed to schedule each vessel.
Finding order in chaos
More specifically, the construction heuristic uses what is called a priority list of vessels at which it inserts the vessels. When we would alter this order, we can give more priority to some stockpiles within the schedule. The idea is that the fit for these stockpiles improves, enhancing the fit in the stockyard and limiting the total vessel delay. In my thesis, I use three different local search heuristics to find the best vessel order: Squeaky Wheel Optimisation, Genetic Algorithm and Ant Colony Optimisation. Each local search heuristic has its own strengths and weaknesses, which could benefit the solution in different scenarios. For instance, Squeaky Wheel is able to intensely search for improvements in hard scenarios. On the other hand, the Genetic Algorithm is able to diversely search for vessel orders in easier instances. In the end, each local search can be terminated at any second, making the methods very flexible to the situation of the planner.
To confirm whether the local search heuristics are able to find competitive solutions, an exact formulation is used in smaller planning horizons. Future research on this topic is mainly concerned on improving the efficiency of these exact formulations as well as incorporating uncertainty of vessel arrival times.
David Boissevain is a master student in Operations Research and Quantitative Logistics and has completed his master thesis at Ab Ovo.
David Boissevain is a master student in Operations Research and Quantitative Logistics and has completed his master thesis at Ab Ovo. David developed an optimizer for stockyard planning of dry bulk material in a steel production port. In his research, he developed a mixed-integer linear programming model (MILP) and different local search heuristics that schedule the vessels to berths and stockpiles within the stockyard. The schedule is made in such a way that total vessel delay is minimised. As the stockpile fit within the stockyard heavily affects the time at which vessels can unload their material, the main challenge in the problem is to optimise the stockpile placement strategy.
Ab Ovo gives econometric students the opportunity to research complex planning puzzles for the master thesis or PhD. Solving world class planning puzzles has our interest. At Ab Ovo the academic world and the business world come together. If you would like to learn more about Ab Ovo, check out our about us section or please contact us at info@ab-ovo.com.
