Martin Lagerholm, Carsten Peterson and Bo Söderberg Statistical Properties of Unrestricted Crew Scheduling
Problems Abstract: A statistical analysis is performed for a random unrestricted local crew scheduling problem, expressed in terms of pairing arrivals with departures. The analysis is aimed at understanding the structure of similar problems with global restrictions, and estimating their difficulty. The methods developed are of a general nature and can be of use in other problems with a similar structure. For large random problems, the ground-state energy scales like N^{1/2}
and the average excitation like N, where N is the number
of arrivals/departures. The average ground-state degeneracy is such
that the probability of hitting an optimal pairing by chance scales
like 2N2^{-N} for large N. By insisting
on the local ground-state energy for a restricted problem, airports
can be split into smaller parts, and the state space reduced by
typically a factor ~ 2^{Na}, with
N_{a} the total number of airports.
LU TP 97-11 |