Meta-Heuristics for large, dynamic Vehicle Routing Problems

Fleet management and the particular problems of fleet utilization and vehicle routing constitute a major cost factor in the domain of distribution logistics. Thus, companies are interested in exhausting the potential for optimization in this area. Apart from that, efficient planning of ressources in transportation is an important issue for the economy as such. Infrastructure growth is outpaced by the increase in traffic volume and given the fact that congestion is already an issue today this may eventually lead to a breakdown of the traffic system if no action is taken. On the other hand, in the last two decades the scientific community has come up with methods that utilize the improved IT infrastructure to solve complex optimization problems efficiently. Particularly, the class of Meta- Heuristics has significantly outperformed custom made algorithms for small, static optimization problems with respect to solution quality, however at the cost of highly increased computational effort. Thus, for industrial problems of realistic size and for dynamic problems that need to be solved in real time the application of these Meta-Heuristics may not be an option. The goal of this project is to develop hybrid algorithms for vehicle routing with specific emphasis on mechanisms to reduce the computational effort for large or dynamic problems. The main aspects in this context are problem decomposition and the intelligent use of a memory about search history. The algorithms will build on existing local search techniques as well as on our experience with memory-based Meta-Heuristics. However, these basic building blocks will be modified to increase flexibility with respect to problem input data. In a further step different strategies for dynamic vehicle routing will be developed and analyzed using the hybrid algorithms. Among others, new waiting rules and diversion strategies will be proposed based on the existing works on these issues.