Using Tabu search for solving a dynamic multi-terminal truck dispatching problem

In this paper we describe a two-phase based algorithm for a real-life tank truck dispatching problem. It occurs in a company involved in the transportation of raw materials throughout Europe. In the first phase, the algorithm determines the route sequence using a decomposition method. In the second phase the initial routes are improved using a Tabu search method. The Tabu search procedure is based on specific moves which attempt to improve two or three routes at each step. Here, the basic moves consist of insertions and exchanges of arcs in the graph of the problem. The combination of these moves provides interesting compound moves which make it possible to cross regions of infeasible solutions. Computational results on a set of test problems are reported, and comparisons with lower bound calculations indicate that the proposed algorithm rapidly gives solutions that are on average within 8% of optimality.