Abstract
Solving the Vehicle Routing Problem (VRP) is a key to efficiency in transportation and supply chain management. The VRP is a computationally hard problem that comes in many guises. The VRP literature contains thousands of papers, and VRP research is regarded as one of the great successes of OR. An industry of routing tool vendors has emerged. Exact optimization methods of today cannot consistently solve VRP instances with more than 50-100 customers in reasonable time, which is generally a small number in real-life applications. For industrial problem sizes, and if one aims at solving a variety of VRP applications, approximation methods is the only viable approach. In this talk, a brief motivation and introduction to the VRP will be given. We then describe how industrial requirements motivate extensions to the basic, rather idealized VRP models that have received most attention in the research community, and how such extensions can be made. At SINTEF, industrial variants of the VRP have been studied since 1995. Our efforts have led to the development of a generic VRP solver that has been commercialized through a spin-off company. As an illustration, a description of the underlying, rich VRP model and the selected uniform algorithmic approach, which is based on metaheuristics, is given. Examples of applications will be presented, along with results from computational experiments. There is still a need for VRP research to meet industrial requirements, particularly for large-scale instances and complex, rich VRP variants, for instance in the context of routing in combination of inventory management and fleet composition. Examples of ongoing projects will be given. In conclusion, we point to future trends and important issues in further VRP research.