Vehicle Routing in Practice

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. In industry and the public sector, vehicle routing tools provide substantial savings every day. An industry of routing tool vendors has emerged. Exact optimization methods of today cannot consistently solve VRP instances with more than 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, approximative methods is the only viable approach. In this talk, a 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 generic VRP solver that has been commercialized. 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. In many application areas, there is still a gap between industrial requirements and cutting edge VRP methods, particularly for large-scale problems and complex, rich VRP variants. Examples from ongoing projects at SINTEF will be given. We point to future trends and important issues in further VRP research, including the use of parallel and heterogeneous computing.