A Network Flow-Based Tabu Search Heuristic for the Vehicle Routing Problem

We develop a new local search approach based on a network flow model that is used to simultaneously evaluate several customer ejection and insertion moves. We use this approach and a direct customer swap procedure to solve the well-known Vehicle Routing Problem. The capacity constraints are relaxed using penalty terms whose parameter values are adjusted according to time and search feedback. Tabu Search is incorporated into the procedure to overcome local optimality. More advanced issues such as intensification and diversification strategies are developed to provide effective enhancements to the basic tabu search algorithm. Computational experience on standard test problems is discussed and comparisons with best-known solutions are provided.