Information Technology Reference
In-Depth Information
(1)
s.t.:
(2)
1
(3)
0,1
Objective function (1) determines a minimum number of vehicles. Constraints (2)
ensure that each item must be covered by at least a feasible loading selected in the
solution.
4
Column Generation (CG) Technique
A linear programming (LP) relaxation of the set-covering formulation, without inte-
grality constraints on
x
variables, is called master problem (MP). Since MP may con-
tain a very large number of variables, the CG technique, which works with a limited
number of variables, is used. The corresponding LP relaxation model to the partial set
of loadings is called the restricted master problem (RMP). In fact the CG technique is
an efficient approach capable of solving problems with large number of variables.
Using CG, the majority of the loadings are not explicitly considered and RMP is
solved for a partial set of loadings. Based on a solution to RMP in each iteration of
the CG technique more loadings with minimum reduced cost are generated and added
to the RMP step by step to reach the optimal solution to MP.
Suppose that
,
be the set of dual variables associated with the current solu-
tion
to the RMP.
1∑
is defined as reduced cost associated to load-
ing
. Only the feasible loadings with the negative reduced cost can improve the
current solution to the RMP. In each iteration of the CG technique, we must solve the
pricing problem that consists of finding a feasible loading
with minimum nega-
tive reduced cost. If no feasible loading with negative reduced cost exists, then there
is no column (loading) to be added to RMP, and, therefore, the current solution is
optimal to the RMP and MP.
Heuristic Pricing
To guarantee feasible loadings with the negative reduced cost a modification of the
algorithm of Crainic et al. [1] is applied for different items sorting rules. In fact, items
are sorted according to non-increasing values of
,
.
.
,
,
,
,
. These
sorting rules help us to find feasible loadings with negative reduced cost.
For each of the sorted lists of items by the mentioned rules, items are inserted into
a vehicle one after the other using a modified algorithm until the residual capacity of
the vehicle is sufficient to accommodate one more item. If the reduced cost associated
to this feasible loading is negative, it is added to RMP as new column. This method
