Integer Programming-Based Heuristics for Vehicle Routing Problems

Abstract

The vehicle routing problem (VRP) has been an active field of study by operations researchers for over 50 years. Many practical applications have been presented in the literature, and many solution techniques have been developed.

We discuss, develop, and computationally test integer programming-based heuristics for several variants of the standard VRP. We use integer programming to model the split delivery VRP with minimum delivery amounts, the multi-depot split delivery VRP, the period VRP, the standard VRP, and the multi-depot VRP. We apply our heuristics to benchmark problems from the literature and generate many new problems with high-quality, visually-estimated solutions. Our heuristics produce high-quality solutions in a reasonable amount of computer time. Overall, our new IP-based heuristics are very competitive with the best methods found in the VRP literature to date.