When creating the constraint-based column generator, our aim was to facilitate the direct representation of algebraic constraints. The model is based on a vector X of integers. The number of elements in X is an upper bound on the size of any feasible duty (UBdutyLen). To calculate UBdutyLen, we start by summing up the durations of the trips, taken in non-decreasing order. When we reach a value that is greater than maximum working time minutes, UBdutyLen is set to the number of trips used in the sum. Each Xi element, called a cell, represents a single trip and is a finite domain variable with domain [1..NT], where and N is the number of real trips. Trips numbered N+1 to NT are dummy trips. The start time of the first dummy trip equals the arrival time of the last real trip plus one minute and its duration is zero minutes. All the subsequent dummy trips also last zero minutes and their start times are such that there is a one minute idle interval between consecutive dummy trips, i.e., they start at each following minute. Their departure and arrival depots are equal to 0. These choices prevent incompatibilities arising from time intersection and mismatching of depots among the dummy trips. Besides, we avoid the occurrence of dummy trips between real trips in a feasible duty.
Note that, the way UBdutyLen is calculated assures that at least one dummy trip appears in X. Moreover, their start times guarantee that the dummy trips occupy consecutive cells at the end of X. This is on purpose, to facilitate the representation of some constraints.
Five additional vectors were used:
Start, End, Dur, DepDepot and ArrDepot.
The i-th cell of these vectors represents, respectively, the
start time, the end time, the duration, and the departure and arrival depots
of the trip assigned to Xi.
Next, we state constraints of type
), where S is a list containing the
start times of all NT trips.
The semantics of this constraint assures
that the value of
is the k-th element of list Swhere k is the value in Xi.
This maintains the desired relationship between vectors X and Start.
Whenever Xi is updated, e.g. due to constraint propagation,
is also modified, and vice-versa.
Similar constraints are stated between X and each one of the four other vectors.
Now, we can use these new vectors to easily state additional constraints, like:
The constraint on total working time, for each generated duty, is given by:
The constraint on total rest time is:
To respect the constraint on split-shift duties, we impose that at most one of the variables can assume a value greater than Idle_Limit. This is done with an atmost constraint in the following manner: atmost(1,L,0). If list L contains all the variables of Equation (7), this means that at most one of them can assume the value zero.
Changing dummy trips in a feasible duty gives
another duty that is equivalent to the original one. New constraints
were imposed over the X cells in order to force dummy trips to have
only one possible placement in X, given that the real trips had
already been positioned. This is achieved with the following constraints,
where N is the
number of real trips:
|Xi > N||(11)|
There is one final constraint, which is responsible for
assuring that generated duties have an associated negative reduced
cost. Using the formula to calculate the reduced cost of a column
(feasible duty) given in Section 3, this constraint reads:
Various labeling strategies have been tried. The strategy of choosing the next variable to label as the one with the smallest domain (first-fail principle) proved to be the most effective one, after a number of experimental trials. Having chosen a variable, it is necessary to select a value from its domain following a specific order, when backtracking occurs. We tested different labeling orders, like increasing, decreasing, and also middle-out and its reverse. Experimentation showed that labeling by increasing order produced the best results. It would be possible to improve the overall performance of this search strategy by experimenting with more sophisticated techniques. Dynamic backtracking  and nogood assertions  could be used in this model so as to promote an earlier pruning of unpromising branches of the search tree.
A crucial advantage of this hybrid approach over a number of
previous attempts is that it considers all feasible duties.
Therefore, it is not necessary to use specific rules to select, at
the beginning, a subset of ``good'' feasible duties. This kind of
preprocessing could prevent the optimal solution from being
encountered. Instead, with the column generation method, our algorithm
implicitly looks at the set of all feasible duties.