Publications of S. Ricciardelli

This page shows all publications that appeared in the IASI annual research reports. Authors currently affiliated with the Institute are always listed with the full name.

You can browse through them using either the links of the following line or those associated with author names.

Show all publications of the year  ALL, with author Ricciardelli S., in the category IASI Research Reports (or show them all):


IASI Research Report n. 280  (Previous    Next)


Bianco L., Mingozzi A., Ricciardelli S., Spadoni M.

Algorithms for the crew scheduling problem based on the set partitioning formulation.

ABSTRACT
In this paper the Crew Scheduling problem (CSP) is formulated as the problem of determining a set of disjoint paths covering all the vertices of an acyclic graph so as to satisfy the problem constraints and to minimize the sum of the path costs. We give a Set Partitioning formulation of the problem and we describe a procedure to compute a lower bound to the CSP that does not require the a priori generation of the entire Set Partitioning matrix. We formulate an exact dynamic program that makes use of bounding functions to eliminate redundant states. We discuss heuristic rules to be incorporated in the exact dynamic program that drastically reduce the size of the state space graph. However, the resulting heuristic algorithms, under certain circumstances, can prove the optimality of the solution produced or provide an estimate of the distance from optimality that is better than the distance between the initial lower bound and the optimal solution cost.
back
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -