The Column Generator

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 *X*_{i} 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 *X*_{i}.
Next, we state constraints of type
`element(`
`)`, 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 *S*where *k* is the value in *X*_{i}.
This maintains the desired relationship between vectors *X* and *Start*.
Whenever *X*_{i} 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:

for all . Equation (4) guarantees that trips overlapping in time are not in the same duty. Since the maximum number of depots is two, an incompatibility between consecutive trips occurs only when the ending depot is 1 and the starting depot is 2, or vice-versa. Equation (5) forbids that situation. Additionally, the consecutiveness of two dummy trips is permitted (for the sum of their depots equals 0) and the appearance of the first dummy trip after the last real trip in a duty is not precluded by this constraint, because the sum of the depots in this case can only assume the values 1 or 2. With a one-depot instance, these constraints are not necessary and they are omitted, together with the

The constraint on total working time, for each generated duty, is given by:

where is a binary variable such that if and only if .

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,
for all
,
where *N* is the
number of real trips:

(10) | |||

X_{i} > 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:

(12) |

For each

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 [5] and *nogood* assertions
[7] 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.

#Trips | #FD | Opt | DBR | #CA | #LP | #Nodes | PrT | LPT | TT |

10 | 63 | 7 | 7 | 53 | 2 | 1 | 0.08 | 0.02 | 0.12 |

20 | 306 | 11 | 11 | 159 | 4 | 1 | 0.30 | 0.04 | 0.42 |

30 | 1,032 | 14 | 14 | 504 | 11 | 1 | 1.48 | 0.11 | 2.07 |

40 | 5,191 | 14 | 14 | 1,000 | 26 | 13 | 8.03 | 0.98 | 9.37 |

50 | 18,721 | 14 | 14 | 1,773 | 52 | 31 | 40.97 | 3.54 | 45.28 |

60 | 42,965 | 14 | 14 | 4,356 | 107 | 41 | 00:04:24 | 14.45 | 00:04:40 |

70 | 104,771 | 14 | 14 | 2,615 | 58 | 7 | 00:01:36 | 4.96 | 00:01:42 |

80 | 212,442 | 16 | 16 | 4,081 | 92 | 13 | 00:01:53 | 18.84 | 00:02:13 |

90 | 335,265 | 18 | 18 | 6,455 | 141 | 11 | 00:02:47 | 31.88 | 00:03:22 |

100 | 496,970 | 20 | 20 | 8,104 | 177 | 13 | 00:06:38 | 51.16 | 00:07:34 |

110 | 706,519 | 22 | 22 | 11,864 | 262 | 21 | 00:16:53 | 00:02:28 | 00:19:31 |

125 | 1,067,406 | 25 | 25 | 11,264 | 250 | 17 | 00:19:09 | 00:01:41 | 00:21:00 |

#Trips | #FD | Opt | DBR | #CA | #LP | #Nodes | PrT | LPT | TT |

20 | 978 | 6 | 6 | 278 | 7 | 1 | 2.11 | 0.08 | 2.24 |

30 | 2,890 | 10 | 10 | 852 | 19 | 1 | 9.04 | 0.20 | 9.38 |

40 | 6,705 | 13 | 13 | 2,190 | 48 | 1 | 28.60 | 1.03 | 30.14 |

50 | 17,334 | 14 | 14 | 4,220 | 94 | 3 | 00:01:22 | 3.95 | 00:01:27 |

60 | 45,236 | 15 | 15 | 8,027 | 175 | 1 | 00:03:48 | 14.81 | 00:04:06 |

70 | 107,337 | 15 | 15 | 11,622 | 258 | 1 | 00:07:42 | 40.59 | 00:08:37 |

80 | 256,910 | 15 | 15 | 8,553 | 225 | 1 | 00:10:07 | 47.12 | 00:10:58 |

90 | 591,536 | 15 | 15 | 9,827 | 269 | 1 | 00:14:34 | 00:02:04 | 00:16:43 |

100 | 1,180,856 | 15 | 15 | 13,330 | 375 | 1 | 00:39:03 | 00:04:37 | 00:43:49 |

110 | 2,015,334 | 15 | 15 | 13,717 | 387 | 1 | 01:19:55 | 00:03:12 | 01:23:19 |

120 | 3,225,072 | 16 | 16 | 18,095 | 543 | 13 | 04:02:18 | 00:09:09 | 04:11:50 |

130 | 5,021,936 | 17 | 17 | 28,345 | 874 | 23 | 06:59:53 | 00:30:16 | 07:30:56 |

140 | 8,082,482 | 18 | 18 | 27,492 | 886 | 25 | 13:29:51 | 00:28:56 | 13:59:40 |

150 | 12,697,909 | 19 | 19 | 37,764 | 1,203 | 25 | 21:04:28 | 00:49:13 | 21:55:25 |