Problems related to crew planning and scheduling in a railroad company

The aim of the paper is first of all to describe and formulate some mathematical programming problems, which arise in a railroad company, and which are at present unsolved, at least as it regards large-scale real situation. Problems of such a king are crew and manpower planning, optimal time-table determination. For the crew scheduling problem a new algorithm is proposed which is based on the upper bound linear assignment algorithm. The optimal time-table problem is formulated as an optimal vertex-packing on an undirected graph, with additional linear integer constraints; this integer linear program is structured, i. e., it has a block angular matrix of the constraining system. Computational experience has been made on a sample of real problems coming from the Italian railroad company.