Global and Local Moves in Tabu Search: A Real-Life Mail Collecting Application

The problem we deal with is the optimization of mail collecting at several customer sites that are scattered around an urban area. It involves the design of a set of minimum cost routes, originating and terminating at a central depot, for a fleet of vehicles that service those customer sites with known demands. We develop a Tabu Search approach where at each iteration the best move is selected among a large variety of possible moves. This new version of the metaheuristic Tabu leads us to determine a good vehicle fleet mix (cheapest cost incorporating routing and fixed vehicle costs) without violating constraints such as time restrictions and capacity.