Computational Results

When compared to the pure approaches, the hybrid approach was able to construct an optimal solution to substantially large instances of the problem, in a reasonable time. Computational results for OS 2222 and OS 3803 appear on Tables 2 and 3, respectively. Column headings have the following meanings: #Trips is the number of trips; #FD stands for the number of feasible duties; Opt is the value of the optimal integer solution; DBR is the dual bound at the root node of the branch-and-bound enumeration tree; #CA is the number of columns added throughout each execution; #LP is the number of linear programming relaxations solved; and #Nodes is the number of tree nodes visited. The execution times are divided in three columns: PrT is the time spent generating columns; LPT is the time spent solving linear programming relaxations and TT is the total execution time. Note that, in every instance tested, the dual bound at the root node was equal to the value of the optimal integer solution. Hence, the LP relaxation of the problem already provided the best possible lower bound on the optimal solution value. Also note that the number of nodes visited by the algorithm was kept small. The same behavior can be observed with respect to the number of added columns.

It is interesting to note, in the last three columns of each table, that the time taken to solve all linear relaxations of the problem was a small fraction of the total running time for both data sets.

From Table 2, we see that the hybrid approach was capable of constructing a provably optimal solution for the complete smaller data set using 21 minutes of running time on a 350 MHz desktop PC. That problem involves in excess of one million feasible duties.

The structural difference between both data sets can be appreciated by observing the entries on the line associated with 100 trips, in Table 3. The number of feasible duties on this line corresponds, approximately, to the same number of feasible duties that are present in the totality of 125 trips of the first data set, OS 2222. Yet, the algorithm used roughly twice as much time to construct the optimal solution when running over a test case that contained the first 100 trips of the larger data set, as it did when taking the 125 trips of the smaller data set. The existence of two depots in OS 3803, rather than a single one in OS 2222, seems to be at the origin of the increased problem complexity of this instance.

Finally, when we fixed a maximum running time of 24 hours, the algorithm was capable of constructing a solution, and prove its optimality, for as many as 150 trips taken from the larger data set. This corresponds to an excess of 12 million feasible duties. It is noteworthy that less than 60 MB of main memory were needed for this run to reach completion. A problem instance with as many as entries would require over 1.8 GB of main memory, if needed to be loaded into main memory. By efficiently dealing with only a small subset of the feasible duties, our algorithm managed to surpass the resource consumption bottlenecks faced by the pure approaches and could solve instances that were very large. This observation supports our view that a declarative constraint formulation of column generation, embedded inside a branch-and-bound framework, was the right technique to solve these very large crew scheduling problems.