next up previous
Next: Computational Results Up: A Hybrid Approach Previous: A Hybrid Approach

   
The Column Generator

Modeling with finite domain constraints is rapidly gaining acceptance as a promising declarative programming environment to solve large combinatorial problems. All models described in this section were formulated using the ECLiPS${}^e\,$ 5 syntax, version 4.0. Due to its large size, the ECLiPSe formulation for each run was prodiced by a program generator that we developed in C.

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 $NT=N + \emph{UBdutyLen} - 1$ 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 element( $X_{i},S,\emph{Start}_{i}$), where S is a list containing the start times of all NT trips. The semantics of this constraint assures that the value of $\emph{Start}_{i}$ 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, $\emph{Start}_{i}$ 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:

   
$\displaystyle \emph{End}_{i}$ $\textstyle \leq$ $\displaystyle \emph{Start}_{i+1}$ (4)
$\displaystyle \hspace{-3ex} \emph{ArrDepot}_{i} + \emph{DepDepot}_{i+1}$ $\textstyle \neq$ 3 (5)
$\displaystyle \emph{Idle}_{i}$ = $\displaystyle \emph{BD}_{i} \times \big(\emph{Start}_{i+1} -
\emph{End}_{i}\big)$ (6)

for all $i \in \{1, \ldots, \emph{UBdutyLen}-1\}$. 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 ArrDepot and DepDepot vectors. Some other constraints are expressed using the $\emph{Idle}_{i}$variables of Equation (6). The binary variables $\emph{BD}_{i}$, in (6), are such that $\emph{BD}_{i}
= 1$ if and only if Xi+1 contains a real trip.

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

 
$\displaystyle \emph{TWT}$ = $\displaystyle \sum_{i=1}^{\emph{UBdutyLen}-1} \emph{Dur}_{i} +
\sum_{i=1}^{\emph{UBdutyLen}-1} \emph{BI}_{i} \times
\emph{Idle}_{i}$ (7)
$\displaystyle \emph{TWT}$ $\textstyle \leq$ $\displaystyle \text{\emph{maximum working time}}$ (8)

where $\emph{BI}_{i}$ is a binary variable such that $\emph{BI}_{i} = 1$ if and only if $\emph{Idle}_{i} \leq
\emph{Idle\_Limit}$.

The constraint on total rest time is:

 \begin{displaymath}\sum_{i=1}^{\emph{UBdutyLen}-1} \emph{Idle}_{i} + \max\{0, \emph{Workday}
- \emph{TWT}\} \geq \emph{Min\_Rest}
\, .
\end{displaymath} (9)

To respect the constraint on split-shift duties, we impose that at most one of the $\emph{Idle}_{i}$ 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 $\emph{BI}_{i}$ 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 $i \in \{1, \ldots, \emph{UBdutyLen}-1\}$, where N is the number of real trips:

$\displaystyle X_i \leq N$ $\textstyle \Rightarrow$ $\displaystyle (X_{i+1} > N \Rightarrow X_{i+1} = N + 1)$ (10)
Xi > N $\textstyle \Rightarrow$ $\displaystyle X_{i+1} = X_i + 1 \, .$ (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:

\begin{displaymath}\sum_{i=1}^{\emph{UBdutyLen}} C_i > 1 \, .
\end{displaymath} (12)

For each i, Ci is determined by element( Xi,V,Ci), where V is a list whose elements are the values of the dual variables associated with each trip. The dual variables associated with dummy trips are assigned the value zero.

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.

 
Table 2: OS 2222 data set (1 depot)
#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
 


 
Table 3: OS 3803 data set (2 depots)
#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
 


next up previous
Next: Computational Results Up: A Hybrid Approach Previous: A Hybrid Approach

1999-12-16