Two-layer simulated annealing and tabu search heuristics for a vehicle routing problem with cross docks and split deliveries

Cross docking plays an increasingly important role in improving the efficiency of large-scale distribution networks. Unlike traditional warehouses, cross docks hold little or no inventory. Instead, goods from incoming trucks are unloaded and immediately transferred through the cross dock to outgoing trucks. Thus, cross docks serve to reduce inventory holding costs and shorten lead times from suppliers to retailers. However, to fully realize these benefits, trucks must be effectively coordinated at each cross dock. Such coordination brings a challenging extension to vehicle routing problems. In this paper a new vehicle routing problem with cross docks and split deliveries is proposed. A mixed-integer linear programming formulation is established for this problem, along with solution methodologies combining a constructive heuristic with two-layer simulated annealing and tabu search. The constructive heuristic creates a solution which is further improved by two-layer variants of simulated annealing or tabu search. The first layer optimizes the allocation of trucks to cross docks while the second layer optimizes the visitation order to suppliers and retailers for trucks assigned to each cross dock. Experimental results demonstrate that the proposed approach effectively solves large-size problems within a reasonable computational time.