Variable neighborhood search based algorithms for crossdock truck assignment

Univ. Artois, UR 3926, Laboratoire de Génie Informatique et d’Automatique de l’Artois (LGI2A), F-62400 Béthune, France

^* Corresponding author: cecilia.daquin@univ-artois.fr

Received: 23 September 2019
Accepted: 3 August 2020

Abstract

To operate a cross-dock successfully, an efficient assignment of trucks to docks is one of the key decisions. In this paper, we are interested in the cross-dock assignment of trucks to docks problem, where the number of trucks exceeds the number of docks. The objective is to minimize the cost of transferring goods within the cross-dock while avoiding delivery penalties. This problem being NP-hard, we use Variable Neighborhood Search metaheurisitc (VNS) to solve it approximately. More specifically, we conduct a structured empirical study to compare several VNS configurations and to find which is/are the most effective for this cross-dock problem. In this work, first we analyze the way the search strategy and the neighborhood operators can be combined in a VNS framework according to their efficiency within a local search. Then the best configurations are tested within three VNS variants, namely Basic VNS (BVNS), General VNS (GVNS) using Basic VND (B-VND) and GVNS using Union VND (U-VND) according to the number of used operators and the order of applying these operators. Finally we evaluate the influence of the stopping criterion within these variants. Some significant differences among these configurations are shown and illustrated by conducting the Friedman test.