A Column Generation for Locomotive Scheduling Problem in Molten Iron Transportation

Molten iron transportation in an iron and steel enterprise involve moving loaded torpedo cars with hot molten iron and empty torpedo cars by locomotives between blast furnaces and steelmaking plants. This paper considers the locomotive scheduling problem, one of the most complex routing problems where both pickup and delivery operations are included. It consists in finding one feasible schedule for each locomotive in order to satisfy all moving requests and in such a way that the concerned costs are minimized. We consider a set-partitioning model of such problem whose columns represent locomotive schedules. We then apply a column generation algorithm for solving the LP relaxed model and a branch and bound algorithm for obtaining integer solutions. Computational experiments demonstrate that the proposed algorithm is capable of solving problems with industrial size to optimality within a reasonable computation time.