In a cross-dock facility, goods are moved by forklift from incoming truck platforms (strip doors) to temporary holding areas and then to outgoing truck platforms (stack doors) or directly from strip doors to stack doors. Costs within the cross-dock may be minimized by appropriate assignment of strip doors to incoming trucks and stack doors to outgoing trucks, thus minimizing the distances that forklifts must travel. Optimizing strip and stack door assignments given the shape of the cross-dock and the origin-destination volumes of goods is known as the Cross-dock Door Assignment Problem (CDAP). The CDAP is very difficult for exact methods because of its quadratic objective function. We propose two heuristics for this problem, one ad-hoc using local search, and the other a metaheuristic called CH (for Convex Hull), designed explicitly for quadratic 0-1 problems with linear constraints. We then compare the proposed heuristics with one exact solution method for optimizing door assignments at typical cross-dock layouts having as many as 20 doors, 20 origins and 20 destinations and randomly generated origin-destination volumes of trucked goods.
Submitted to Matheuristics 2012, www.ic.uff.br/matheuristics2012/