USING TABU SEARCH FOR SOLVING A DYNAMIC MULTITERMINAL 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 me thod. In the second phase the initial routes are improved using a Tabu search method. The Tabu search procedure is based on specific moves w hich attempt to improve two or three routes at each step. Here, the ba sic moves consist of insertions and exchanges of arcs in the graph of the problem. The combination of these moves provides interesting compo und moves which make it possible to cross regions of infeasible soluti ons. 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 opt imality.