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 ECLⁱPS${}^e\,$ ⁵ syntax, version 4.0. Due to its large size, the ECLⁱPS^e 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 X_i 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 X_i. 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 X_i. This maintains the desired relationship between vectors X and Start. Whenever X_i 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:

   

$$\emph{End}_{i} \leq \emph{Start}_{i+1}$$ (4)

$$\hspace{-3ex} \emph{ArrDepot}_{i} + \emph{DepDepot}_{i+1} \neq$$ 3 (5)

$$\emph{Idle}_{i} \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 X_i+1 contains a real trip.

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

 

$$\emph{TWT} \sum_{i=1}^{\emph{UBdutyLen}-1} \emph{Dur}_{i} + \sum_{i=1}^{\emph{UBdutyLen}-1} \emph{BI}_{i} \times \emph{Idle}_{i}$$ = (7)

$$\emph{TWT} \leq \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:

$$\sum_{i=1}^{\emph{UBdutyLen}-1} \emph{Idle}_{i} + \max\{0, \emph{Workday} - \emph{TWT}\} \geq \emph{Min\_Rest} \, .$$ (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:

$$X_i \leq N \Rightarrow (X_{i+1} > N \Rightarrow X_{i+1} = N + 1)$$ (10)

$$\Rightarrow X_{i+1} = X_i + 1 \, .$$ 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:

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

For each i, C_i is determined by element( X_i,V,C_i), 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