Tabu Search Algorithm for the Vehicle Routing Problem with Cross - Docking
by Ms. Amalia Nikolopoulou, Doctoral Candidate
Cross-docking is a distribution strategy often found in multi-echelon supply networks. The basic idea behind this strategy is the minimization of inventory costs, appearing in multi-echelon distribution with intermediate facilities, by reducing warehouses and distribution centers to purely transshipment facilities (cross-docks) which do not hold inventory. In a typical cross-docking system, the products arrive at the cross-dock from the manufacturer, where allocated outbound vehicles are immediately loaded with the packages before delivering them to the retailers. Goods are therefore stored in the cross-dock for a short time, or are directly dispatched to customers through a consolidation process which allows products to be classified and loaded to the delivery vehicles.
In this work we consider the so-called Vehicle Routing Problem with Cross-Docking (VRPCD). The problem objective, as defined by Wen et al. , is to design minimum cost routes for the transportation of products via a cross-dock, considering supplier-customer pairs with known demand. Each node must be served by exactly one vehicle within its time window and the accumulated load of each pickup - delivery route must not exceed the vehicle capacity. Concerning consolidation decisions at the cross-dock, two scenarios are considered. In the first scenario, the same vehicles are used to perform the pickup and delivery routes. In this case, for a given supplier-customer pair i-j, products from i have to be unloaded at the cross-dock if the vehicle will not service the paired customer j in its delivery route. Similarly, if a vehicle services customer j but does not service the paired supplier i, then the delivery products have to be loaded at the cross-dock. In the second scenario, different vehicles are used to perform the pickup and delivery routes. Therefore, all products in the pickup vehicle need to be unloaded at the cross-dock and are then loaded to a delivery vehicle.
An efficient Tabu Search algorithm is proposed for solving the problem. The algorithm uses the concept of promises to enhance diversification during the search process . More specifically, when a move is implemented, some solution attributes (arcs) are eliminated and some others are generated. The eliminated solution attributes are associated with a promise tag equal to the solution cost, before the implementation of the move. To that end, tentative moves within the local search process are allowed only if their implementation will lead to the generation of solution attributes with lower cost than the promise tag of these attributes. The proposed algorithm was tested on realistic data sets involving up to 200 pairs of nodes, and improved the best known solutions from the literature for most problem instances . Computational results also demonstrate that the algorithm can provide high quality solutions within reasonable computational times.
1. M. Wen, J. Larsen, J. Clausen, J.F. Cordeau, G. Laporte (2009). Vehicle Routing with Cross-Docking. Journal of the Operational Research Society. Vol. 60, pp. 1708-1718.
2. E.E. Zachariadis, C.D. Tarantilis, C.T. Kiranoudis (2012). The Pallet Packing Vehicle Routing Problem. Transportation Science 46(3), 341-358.
3. C. D. Tarantilis (2012). Adaptive Multi-Restart Tabu Search Algorithm for the Vehicle Routing Problem with Cross-Docking. Optimization letters, p.1-14.