A Large Neighborhood Search for a Rich Vehicle Routing Problem arising in the Steel Industry

We study a variant of the vehicle routing problem inspired by a real world problem setting that occurs in steel producing factories. Steel slabs are heterogeneous items that appear at locations at certain release times and, according to their handling instructions, need to be transported to another
location within the factory before a certain due time. They are transported by fleets that include standard vehicles as well as truck-and-trailer type vehicles. In our model, practitioners impose high processing rates such that not all steel slabs can be delivered in time during the considered optimization period. Therefore, the objective function is organized in a lexicographic fashion: first, maximize the throughput-related profit; second, minimize travel times. Exact solutions can only be obtained for small problem settings. In order to solve large real world instances, we propose an algorithm based on Large Neighborhood Search. The results of our approach show that the solutions obtained are competitive compared to the solutions provided by our industrial partner.