A tabu search heuristic for a full-load, multi-terminal, vehicle scheduling problem with backhauling and time windows

The problem considered is the full-load pickup and delivery problem with time windows, and heterogeneous products and vehicles, where the assignment of pickup points to requests is not predetermined. Elements associated with tabu search, such as diversification by reversion to ‘junctions’ and the use of soft aspiration criteria, are embedded into our tabu search implementation. This metaheuristic is evaluated using random instances and selected data from a construction company in the UK. The obtained results are compared against lower bounds from LP relaxation and also solutions from an existing multi-level heuristic.